Found my solution! The problem was with carriage returns (who knew?):
function CleanString($varstring) {
$varstring = stripslashes($varstring);
$varstring = '<p>' . $varstring . '</p>';
$varstring = str_replace("\r", "\n", $varstring); // the correction
$varstring = str_replace("\n", "</p><p>", $varstring);
$varstring = str_replace("<p></p>", "", $varstring);
return $varstring;
}
Alternately, there's a slightly more robust solution at
http://www.photomatt.net/scripts/autop for anyone experiencing similar trouble.
Confidence is what you feel when you do not truly understand the situation.