The draw back of nl2br is that it produces <br>, which if you are creating XHTML compliant pages are not valid. That is why str_replace is better as you can replace the new lines with the compliant <br />.
On php.net however, in one place they say it replaces it with <br />, and in other places it says <br>.
You are losing the visible newlines because HTML ignores newlines - in HTML you have to have <br> or <br /> tags instead. The newlines are stored in the browser, but when stuff is outputted to HTML they are no longer visible unless you replace them with <br> tags.
This is a GOOD thing. There are many applications that do NOT require <br> tags to generate new lines - such as e-mail sending. If the data was stored in the database with <br> tags instead of newlines it would make it much harder to use the data in situations other then HTML, such as formatting data for hand held PCs or e-mailing articles to people.