OSによって改行コードはまちまちだからそれに併せて変更してあげないといけない。とりあえずこんな感じでやってみた。うまく行っているように見えるのでたぶん大丈夫でしょう。
$str = str_replace("\r\n", "\r", $str); $str = str_replace("\r", "\n", $str); $str = str_replace("\n", "<br />", $str);
Windows系が\r\nでMac/Unix系が\rらしい。詳しく調べてないから間違ってるかも。