I have the same problem too.
Same problem here! Sitemap was working well on 1.4 version I upgraded to 1.7 recently...why would I check if my sitemap is visable for google and other search engines after just an magento upgrade?!
Well that was a mistake :(
I noticed few days ago that google can’t even find my sitemap. The most fumiest thing is that sitemap gets generated everyday, same time (cron) and sitemap is exactly were its supposed to be. But if I browse through any browser and use the same path for the URL it gives 404 error. Browser = Google :( :( :(
Does anybody know anything about this? htaccess??