So to be on the same track: We are all talking about an unwanted output before the xml tags start, so the sitemap will fail to parse.
Possible problems as discussed so far:
1) WordPress 3.6
2) Plugin incompatibility
3) Size malfunction
4) Execution time malfunction
Lets rule some of these out.
1) and 2) might not be the problem – I got the error running 3.5. Transferring all the data to another webhoster couldnt reproduce the error (remember: Transferring ALL data – plugins, theme, database, etc).
So 3) wont be the problem neither – because the error would have come up on the other webhost aswell.
4) reducing the amount of data to process (and therefore reducing execution time) solved the case for me. For others it didnt – so this might be one trigger, but its very likely that there are others involved too.
Another guess: Did any of you manually import data into the wordpress database?
After I did, the error showed for the first time. After manually checking my database entries I found a strangely formatted entry, rewrote this – and got still an error (but a different output before the xml).
Perhaps its a combination of those two factors: Execution time, and wrongly formatted entries?