Geee it's killing me. I don't know why, but I can't get my sitemap accept through the google verification system. the sitemap plugin even creats the page but google says it's not existing. :-/
I had trouble too. What I did was go to the sitemap and then save it to a file on my hd and then submit to google and that worked better.
I have many clients at AutoMapIt using Drupal as their CMS and I've heard that it's tough to find something that works well for Drupal. Are you using the Drupal URL rewrite or standard URLs?
Perhaps you could post the url of the where your sitemap is / supposed to be. Could be header issue (wild guess)