The problem for me was that I was logged in a Domain Administrator, but not as the Backup Exec Domain Account. I created a new set of credentials and used the Domain Admin account that I was logged in as, and it worked fine. Presumably if I had logged in using the BE Domain Account it would have worked as well.
Hope this helps.
Sam
UPDATE:
It turns out that the problem was with the password for the Backup Exec Domain Account. Info
here. To summarize, the password can not contain & " < or >.
The password can not be started with a - and must not end with a % \ or ^
Presumably there is a script which hands the credentials over to Postgres which has the above limitations.