Why didn't you mention what type of phone and what firmware is used?... those things are important. As is knowing whether the phone has the locale to actually display such characters (earlier phone loads couldn't handle any non 7bit ASCII characters unless they had the appropriate locale loaded).
And you might have to try with the character encoding appropriate for your type of phone.. most of my phones (all the latest loads, and either English, German, French or Italian locales) accept pushed data (not via POST though.. I do it via JTAPI) if I prepend the following header (that codepage is the codepage we use locally)
Older loads didn't accept any xml tags before CiscoIPPhone elements (hence the first remark.. with still a bunch of CCM 4.0/1 and even 3.x versions out there those installations may have seen the last firmware load upgrade years ago).