Hola Lchavodel8, estuve revisando tu codigo y me está funcionando correctamente, lo único que se me ocurre es que la cadena que te está llegando de la DB no viene como lo indicas "\r\n", revisa que realmente te esté llegando eso, si puedes copiar la cadena que tiene el vector sería mejor...
Probé con esto y funcionó ok:
Código PHP:
<?php
$row_ChatStaff['mensaje'] = "Hola \r\n Bien";
$llamo = preg_replace("/\r\n/","</br>",$row_ChatStaff
['mensaje']);
echo $llamo; ?>