伊東です。
＃すでに自己解決されているようですが、思いついたので投稿。
> すみませんが、ereg_replaceでなんとかならないでしょうか。
php.ini の mbstring.func_overload を4（〜7）にして
$message = ereg_replace("http://([[:graph:]\S\$\+\?\.-=_%,:@!#~*/&]+)",
"'<a href=\"http://www.example.com/redirect.php?u='.urlencode('http://\\1').
'\" target=\"_blank\">http://\\1</a>'", $message, 'e');
にする。
＃ていうか、掲示板ならマルチバイト対応の関数使えよと思（略