Did you have any luck with this?
If I don’t urlencode, but just sub out spaces with +
$twitterMessage = str_replace(” “, ‘+’, $twitterMessage);
that fixes my spaces, but extra characters like ‘ or : still come up garbled in FF. OK in Safari, oddly enough.