General HTTP error: 404 not found

I installed the latest sitemap module. Now I'm trying to submit my sitemap to google for the first time. My sitemap's URL is http://mydomain.com?q=sitemap.xml and I can see it with my browser. When I enter the url and send it to google I get the following error:
General HTTP error: 404 not found
We encountered an error while trying to access your Sitemap. Please ensure your Sitemap follows our guidelines and can be accessed at the location you provided and then resubmit.

Any clue why I get the error? Sitemap shows fine when I navigate to the URL.