Its not a problem with the encryption on those shares, this is a default behaviour of Backup Exec. Whenever you create a user share on any NAS, the NAS will try to emulate windows in order to create these shares and when Backup Exec tries to back it up it detects that false windows emulation of NAS and will give you an error about remote agent not being present.
This issue has been acknowledged by Symantec, see
http://support.veritas.com/docs/242619 for more details about this issue.
If this answers your question, please mark this as "Sollution"