Are you using the Contact Form Solution pack?
If so, take a look at the WA_UniversalEmail/Templates/contactus.php file.
look for the following line:
<?php echo(str_replace("\n","<BR />",$pval)); ?>
and change it to:
<?php echo(str_replace("\r\n","<BR />",$pval)); ?>
When a PHP warning occurs, it does not stop the page from processing, it just displays the error, and continues along processing the rest of the code on the page.
In the case, the output that is causing the headers already sent error to occur, is the Warning.
When the Headers Already sent error is proceeded by another warning error message, it should be ignored.