Trillian has probably changed a lot from the last time you tried it. They let their free version stagnate for the longest time, before finally rewriting it in parallel with their pro version.

Though, if you do look at a replacement to ICQ, I'd say look towards Miranda first. It's a very basic IM program. Trillian has expanded to try and do a lot of things and be very flexible, and to me it seems a bit much for basic IM now.