I had the same problem. WordPress is installed in the web root and I’ve chmoded two blank files, sitemap.xml and sitemap.xml.gz to 777. No joy.
However, if I build the sitemap manually the first time there is no problem and the appropriate files get written to.
I have yet to see if the plugin will automatically build the sitemap.