I had the exact same problem for my dashcams store. Magento was returning error saying "Unable To generate Sitemap" .
First of all i did database maintenance. you can google for a tutorial on how to run magento database maintenance.
2nd i went to System > Configuration > Developer and Enabled Log in Log settings.
This log file gets stored in var/log folder.
I tried to create sitemap again and error log was created. checked log and found that it was SQL error for on of extensions which i had already uninstalled.
I went to app/etc/modules . I opened .xml file for that extension and replaced word "true" with "false" . It switches off the extension.
i cleaned cached i.e. deleted everything inside var/cache folder.
then i tried sitemap generation again and it worked.
i didall this via cpanel.
