This question has been answered by andytough. See the first response.
if (!function_exists('smarty_mb_str_replace'))
The smarty_mb_str_replace function is using mb_split, which relies on the character encoding specified by mb_regex_encoding. Given that, I don't see how Smarty's mb_str_replace implementation is encoding-aware
I ended up finding the root cause of the problem was not with mbstring which was enabled, it was with mbregex, which was disabled by default for some reason. I rebuilt apache/php with mbregex enabled and all is well.