Sí porque en sistemas linux se usa el \n únicamente por lo que \r\n no sería encontrado por str_replace() y no realizaría el reemplazo. Lo que puedes hacer es montarte una función que haga ambos reemplazos o que tenga en cuenta el SO para hacer una cosa u otra y así no tienes siempre que estar cambiando esto.
Código PHP:
function My_nl2br($str) {
// Primero siempre el \r\n
return str_replace("\n","<br />", str_replace("\r\n", "<br />", $str));
}