http://jsfiddle.net/ksevelyar/4x6Qf/10/
output = ('<p>'+input.replace(/\n\n+/g,'</p><p>').replace(/[^>]\n/g, "<br />")+'</p>');
upd:
В целом абзацы и переносы строк создаются нормально, но до того момента как парсер натыкается на блочный html, например h2. Он пытается засунуть заголовок внутрь p, после чего браузер звереет и берёт инициативу на себя.
Нужно задать список всех блочных элементов и вставлять </p> перед и <p> после.
Отпишу в топик как что-нибудь получится.