Code:

<?php
function nls2p($str)
{
  return str_replace('<p></p>', '', '<p>'
       . preg_replace('#([\r\n]\s*?[\r\n]){2,}#', '</p>$0<p>', $str)
       . '</p>');
}
?>

Code:

<?php
echo nl2br(nls2p("Paragraph1\n\nParagraph2\n line1\n line2\n"));
?>

Code:

<p>Paragraph1<br />
<br />
Paragraph2<br />
 line1<br />
 line2<br />
</p>

Code:

<?php
echo nl2br(nls2p("Paragraph1\r\n\r\nParagraph2\r\n line1\r\n line2\r\n"));
?>

Code:

<p>Paragraph1</p><br />
<br />
<p>Paragraph2<br />
 line1<br />
 line2<br />
</p>