Was this other header(s) removed for security reasons?
If so, do you have an extra CRLF on the end of your last header? The PHP manual is confuzzling me a bit... if you dont have a CRLF on your last header, add one. If you do have one, remove it.
Try an e-mail again and let me know if that changed anything.
Also, what version of PHP are you running and on what O/S ?
EDIT: Are any lines in your headers over 78 characters (excluding CRLF) ?
EDIT2: RFC 2822 says terminate headers with CRLF so... make sure you have a terminating CRLF on all headers (including last one). There are some more restrictions, such as they must be US-ASCII printible characters, etc.