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.