Hola,
Si lees el manual
www.php.net/nl2br , esta funcion no sustituye los saltos de lines, solo inserta <br /> delante de cada salto de linea. Asi que
\n\n
pasa a ser
<br />\n<br />\n
siendo \n el salto de linea (que varia segun sistema operativo, pudiendo ser \r\n o algo parecido).
Por eso tu str_replace() falla, porque no existe la cadena <br /><br />.
Suerte.