Are other user backups using other policies working? Can you temporarily put a failing client into a working policy and see it that works? Is the policy type set to windows not Standard? If you log on to one of the failing clients can you telnet master_server bpcd from that client? Have you tried the bpclntcmd -pn from the failing client.
I have seen this problem when the master or media server is on a different vlan from the client. The master initiated backup works because it can talk to both the media server and the client, whereas the client initiated backup fails because the client cannot talk to the master or more likely the media server.
Good luck, keep us posted.