RegExp не находит "\n", но они там явно есть.
...
string.replace(QRegExp("\\n"), QString("<br\>"));
\n -- это два символа только в исходном коде, в исполняемом коде это один символ (с кодом 10).
\\n -- это три символа в исходном коде и два -- \n в исполняемом.
А может вообще и заменять не надо и можно используя "\n" заставить QLabel делать переносы текста на новую строку?
В мануале по QLabel есть такой пример:
QLabel *label = new QLabel(this);
label->setFrameStyle(QFrame::Panel | QFrame::Sunken);
label->setText("first line\nsecond line");
label->setAlignment(Qt::AlignBottom | Qt::AlignRight);