How can I log in to ICQ using Messages?
Setting Server to login.icq.com and Port to 5190, unchecking SSL in Server Settings tab should help.
Add:
Enter only the first eight characters of your password, leaving off any extras. This consistently worked for me. I use OSX 10.9 Mavericks and Messages.
Some have had results leaving the last character off their password.