Wanted to add my $0.02 worth on this issue.
Could not upload image files, and no wordpress files had been changed during the time from before, when it worked properly, and after, when it would no longer upload, so there was no extra spaces issue as suggested (with enormous surety) in the FAQ. Yet, still I got the "uploaded file could not be moved to... Warning: Cannot modify header information - headers already sent by (output..." error.
The permission settings were indeed set for 777 within wordpress, via FTP, and via the cpanel interface.
However, something on the web host caused the directories to act as though the permissions were set differently.
So, before trying anything else, I suggest entering cpanel (or you may have vdeck on your web host, or something similar), and go to the File Manager (or the equivalent on your web host). Set the permissions on the ...wp-content/uploads folder to 777 (again).
That may clear the error on the web host, and the error should disappear. Very frustrating when errors appear through no fault of your own. Also frustrating when dozens and dozens of forum postings are left unanswered or left with misleading information because the the issue "has already been answered" yet nowhere is a conclusive, summing-up statement made.
I suggest the something similar to the above solution be added to the wordpress troubleshooting FAQ: http://codex.wordpress.org/FAQ_Troubleshooting#How_do_I_solve_the_Headers_already_sent_warning_problem .