Read this if your index.php is UTF-8 encoded:
Having just solved the exact problem but using a solution not mentioned here, I thought I’d jot down the solution for posterity ?? I use WP 1.2.1.
Make sure your text editor is not writing BOM header to your UTF-8 file! For example, in a power editor like UltraEdit, the configuration setting lets you turn this feature on or off.
After reconverting my index.php to UTF-8 without BOM header, the annoying “header already sent” was gone. Hurray!