Thanks for your reply Sue. It's been a few weeks but we're still stumped on this. As a work around we are deploying manually via the upload function or deploying directing from the server itself for now.
Anyone know of any group policy rules that may cause this issue?
If the URL is correct and you're sure permissions are correct another thing to try is right click on VisualStudio.exe (devenv.exe or whatever it's called) and run as administrator.