I keep having to hunt down the fix for this, as I work with a lot of production SharePoint environments that are not exposed to the web… and this error is symptomatic of the lack of connectivity.
This is the article I used to use http://blog.muhimbi.com/2009/04/new-approach-to-solve-sharepoints.html but this article seems to be a smarter approach… http://technet.microsoft.com/en-us/library/cc753863.aspx
The fix is easy, and can be done through Group Policies (either local or Domain-wide, useful if you are running a separate domain with a 1-way trust to an existing domain).
Group Policies –> Default Domain Policy –> Edit, then…
Change it to:
The other tabs can be left as is, but on this tab both options are selected by default – they need to be unticked.