At a guess, the browser is only sending "\n" as the newline, not "\r\n". Also, you probably want to transpose the order to "</p><p>". You could use a regexp to handle any case, including multiple consecutive newlines:
I have no idea from the code and descriptions provided how it would happen, but what you are showing us seems to indicate that you do not have carriage return and newline characters in there, but literally back-slash, "r", back-slash, "n" -- which is not the same thing as an actual carriage return and newline which are represented in PHP by "\r\n" when within double quotes.
"Please give us a simple answer, so that we don't have to think, because if we think, we might find answers that don't fit the way we want the world to be."
~ Terry Pratchett in Nation