How about:
$tweet = preg_replace("/ +#(\p{Xwd}*)/u", " <a href=\"http://twitter.com/tag/$1\" target=\"_blank\">#$1</a>", $tweet);
\p{Xwd}
has the same meaning that \w
with all unicode letters and number and underscores.
If you don't want underscore, use \p{Xan}
.