You can't simply iterate over a unicode string and expect, that each iteration will receive a full character, if a single character really goes over more than one byte.
Use preg_split
in combination with the unicode modifier to split your string into valid unicode characters. Then use the result of this to replace the characters in the original string.
You could also use one of the multibyte regex functions, such as mb_ereg_replace