Have you tried:
Go to Main > Preferences > Miscellaneous
Select Chinese from the multilingual support drop-down menu. If Chinese isn’t available in that menu,I don’t know where you do to get it though.
I just checked and it is available with the newest ICQ version. I’ve never tried sending messages but have been able to receive messages in both English and Chinese for quite some time, even before the latest upgrade.
However, to my knowledge you will need an input method to make it work for sending messages. I’m not very fond of WinStar as I had major issues with it in the past. If you have Office 2000, XP, or even Windows XP you can get all the Chinese input methods free with installion of these software selections. Since Microsoft upgraded to XP I haven’t seen the IMEs anymore on their site so you might want to consider picking up a copy of one of these to get things rolling.