People are claiming that
xmessage does not support unicode utf-8, or that you should switch to some gnome crap instead. Try specifying the resource
*international: true and it will work as advertised. (You might still have to set up your fonts properly.)
By the way, a proper Gnome-alternative is Zenity.