If you're only interested in the solution, skip to the last line.
Here's what ended up happening. I had a div tag in html that contained certain information.
When a user hits a button, a JS code runs that converts that div to an input textbox, and sets the value of that textbox as the html of the original div - while replacing all occurrences of <br> with \n to create real line breaks.
The form then got submitted via ajax to the server.
When I tried to replace the line breaks in PHP, none of the above suggestions helped, for the simple reason that it wasn't (curiously enough) a "real" linebreak character. What got submitted to the server was the literal \n.
You'd think escaping the backslash in \n, as suggested by ghostdog74 would solve the problem but it did not. I tried escaping it several different ways but nothing seemed to help.
I ended up referencing some old regex material and found that:
Many flavors also support the \Q...\E escape sequence. All the characters between the \Q and the \E are interpreted as literal characters. E.g. \Q*\d+*\E matches the literal text \d+. The \E may be omitted at the end of the regex... This syntax is supported by the JGsoft engine, Perl, PCRE... [source]
Following that, here's the piece of code that solved my problem:
$text = preg_replace('#[\Q\n\E]+#', "\n", $text);
Thank you everybody for all your help! +1 for all :)