Have you looked at yoursite.com/sitemap.php to see if there is content in there?
Does your robots.txt by chance exclude the sitemap.php?
If you can see the sitemap.php by visiting the .php file then the issue is on Google's end most likely as if it wasn't working there would be more people reporting it.
Yes, sitemap.php shows the list of sitemap.php URL's with ?c=1 to ?c=9. If I go to any of those URLs it downloads the xml.gz file. My last line of robots.txt is Sitemap: <sitemap URL>, and it's the correct URL.
What version of XF - I faintly remember one of the earlier versions having issues with the sitemap but do not remember which one it was.
If not the latest 1.5.x then try upgrading to it.
I honestly don't remember what version it was... but it's always a good bet to get up to the latest version to eliminate that. I'm sure there will be something about the releases in the HYS area that give what each version between it and the current fixed.