What theme are you using?
I had the same problem and added the following to beginning of .htaccess
# WordPress SEO – XML Sitemap Rewrite Fix
<IfModule mod_rewrite.c>
RewriteEngine On
RewriteBase /
RewriteRule ^sitemap_index.xml$ /index.php?sitemap=1 [L]
RewriteRule ^([^/]+?)-sitemap([0-9]+)?.xml$ /index.php?sitemap=$1&sitemap_n=$2 [L]
</IfModule>
# END WordPress SEO – XML Sitemap Rewrite Fix
