Have you tried checking GAIM forums? Or have you made any changes to your network and/or firewall settings?
As Thera said, every once in a while I can't connect to ICQ with Miranda. I hit up the Miranda page and see they changed the protocol slightly so I generally just need a new ICQ.dll, or maybe I'm just behind and get the newest client as well.