Sorted!
The proxy we are using would appear to have several different authentication methods available - those enabled were Windows Logon and Anonymous authentication. As soon as we turned basic authentication on it works!

Thanks a lot for your time Bitt.

Cheers.