Ok updated advice:
Do a check to see if your rewrite is working properly, so in .htaccess add:
RewriteRule ^/rwtest
http://www.google.com [R]
Then go to
www.yourdomain.com/rwtest and it should redirect you to Google. If it doesn't then it might be that your host hasn't setup .htaccess properly and you might need to add the rewrite stuff to your httpd.conf file or get them to enable .htaccess.
Once you get test running then this worked for me:
RewriteRule ^/((urllist|sitemap).*\.(xml|txt)(\.gz)?)$ http://www.yourdomain.com/vbseo_sitemap/vbseo_getsitemap.php?sitemap=$1 [L]
Then at Google, for the Sitemap, enter:
http://www.yourdomain.com/sitemap_index.xml.gz
And test it, should work now.