I tried to write a quick script to see what the problem is, but I'm too tired I think.
Try using str_replace like you said, and replace the "\n"s with nothing.
$string = str_replace("\n"," ">",$string);
That'd work, surely.
I think there is an opposite to nl2br somewhere, or writing your own function for that isn't too tricky, but why do you need it?
a "br2nl" function would replace all "<br>"s in the string with "\n"s...
If this doesn't work, post some of the code up here so I can get an idea of what your trying to do.