We are running 6.5.2++ and had a similar issue, we had explicit paths and for some reason it wouldn't deal with sub-directories on the backups until we had the cross mount points attribute set in the policy. Also have you tried using / instead of AL...
I am getting the same problem my master and media servers connect to the client fine, we can ping/telnet both ways. In addition tested ping with 1 MB packets which worked without loss. Name resolution appears to be fine both ways. Backups fail at aro...