Mine started doing this a while ago and I assumed it was some kind of routing error, although I could successful connect to google and bing at the time.

In the end I just switched to BWP Google XML Sitemaps and it works much better.