Para eliminar elementos <br> ubicados inmediatamente después del cierre de un elemento <p> se me ocurre algo como esto:
Código PHP:
// Asumiendo que $original es el texto original antes de aplicar nl2br()
$contenido = nl2br ($original);
while (preg_match ('~(</p>)\\s*<br\\s*\\/?>~is', $contenido, $coincidencias)) {
$contenido = str_replace ($coincidencias[0], $coincidencias[1],
$contenido);
}
// En este punto $contenido ya debe resultar como esperas..
Es un ciclo simple que usa una expresión regular para verificar si se encuentra una etiqueta <br> después de la cadena </p>, y en ese caso reemplaza esos segmentos simplemente con la cadena </p>. Quizás te sea de ayuda para tu programa :).