I seem to have a similar problem. My problem started with new pages not being indexed by Google for over 2 weeks. I have some very old pages indexed by Google, but pages that I have added to my site 2 weeks ago are still not indexed. But I know Google did crawl my site. So, I though of adding a sitemap. I did, and I am getting:
"Your Sitemap does not appear to be in a supported format"
I have no idea why. My site is *.htm document. How did you find out that something redirects all googlebot requests to external site in case of kkey1's? I am wondering if I have the same problem, but I am not sure how to find out. If it helps, I am hosted at 50webs (so, i do not have access to .htaccess). Here is my sitemap if it helps: [external links are visible to admins only]
Any advice much appreciated.