Bueno, realmente es \r\n. De todas formas, no se si esto influira (
http://www.php.net/manual/en/function.mail.php):
Cita: The Windows implementation of mail() differs in many ways from the Unix implementation. First, it doesn't use a local binary for composing messages but only operates on direct sockets which means a MTA is needed listening on a network socket (which can either on the localhost or a remote machine). Second, the custom headers like From:, Cc:, Bcc: and Date: are not interpreted by the MTA in the first place, but are parsed by PHP. PHP < 4.3 only supported the Cc: header element (and was case-sensitive). PHP >= 4.3 supports all the mentioned header elements and is no longer case-sensitive.
Asi que si usas windows, ese puede ser el problema.
Saludos.