Does it work if you switch to the default theme?
I had this same problem. It was fine with the default theme, but complained if I used my own theme. It turned out I had an extra newline at the end of the functions.php file in my theme. So I would guess that something in your theme (I think that functions.php is the only theme that gets called when a feed is generated) or one of your feed-related plugins is inserting that extra newline.
