Well if was permissions stuff I figure this one's probably more relevant, though not overly so http://seer.support.veritas.com/docs/239499.htm
Have you tried mapping the share to a drive, and then creating the B2D referencing that, rather than a UNC share?
Are you running backup exec as the local administrator, or have you created a specific backup exec user? Is Backup Exec definitely trying to connect to the remote server using the same credentials as you are using on the server to connect direct to the server? To confirm it for certain you could try running NTFilemon (free download from http://www.sysinternals.com/Utilities/Filemon.html) on the remote server when you try to create the B2D folder, and see what errors come up, and which login is attempting to login.
If backup exec is trying to connect as a specific local user, you could create the same user on the remote server using the same password, which should then allow the server to connect successfully using those credentials.