I was about to post that I was having the same problem as Super Jinni
When I clicked on the link for my site map:
http://www.mysite.com/sitemap_index.xml
It said: Sitemap file not found
Then I click on "run sitemap generator" and that didn't change anything
I had to walk away for about 45 minutes and now when I login to my sitemap admin area I see a different link:
http://www.mysite.com/sitemap_index.xml.gz
So maybe it just takes time?