Google Sitemaps generating http errors and 404s

The only sitemap generator I have used is this one, and I have a whole slew of 404s (not found) in one site, and 406s (not acceptable) in another. They are all dues to the word permalink being added to every post with a space just before it. In other words, after the actual permalink, such as http://www.example.com/a-permalink/ permalink
Google is crawling them and returning the error. Bug? Or conflict with another plugin?
The thing is, I can’t see this when I look at the sitemap, either online or in a text editor. Anyone else seeing this problem?