Since many people seem to have troubles to log on to ICQ these days (again), I (continue to) suggest Jabber for instant messaging (IM) - not as an additional alternative, but much more as replacement. So if you haven't heard about it yet, this introduction and howto is for you.
In case you haven't heard of it yet: Jabber aka XMPP is an open, XML-based Internet standard for IM. It has some things in common with email, namely its decentralized structure (everyone can run his/her own server an become part of the network; of course, lots of public servers are available) and its use of DNS (a JabberID has the form firstname.lastname@example.org). Also, connections can be encrypted and additional services, including gateways to "legacy" instant messaging networks, are available.
Not only are there many different Jabber clients for even exotic platforms and devices (including Amiga, cellphones and the Sony Playstation Portable), but the technology is also used in various applications, including IM-capable VoIP software like Google Talk, Gizmo Project and (in transition) OpenWengo as well as Web-based services like meebo. Last but not least, the protocol is extensible; one notable example is the VoIP extension "jingle" used in Google Talk.
So, to get some people started, here is a short introduction on how to create a Jabber account using the multi-protocol IM client Miranda IM, my favorite on Windows (although using the word "favorite" in one sentence with Windows seems awkward to me).
If you didn't choose the Jabber plugin during the installation, you can download the plugin now separately. Just unzip the .dll file into your plugins directory.
To be able to use encrypted connections to the server, you will need to install OpenSSL.
Open the options and go to Network → Jabber. Now enter the username and passwort you want to use for your account and fill in the address of the Jabber server (you presumably prefer to choose one of the public servers next to your location) your account should be created on. It may look like this:
The resource string can by anything you like and helps to distinguish the clients you use (since you can use your account from many clients simultaneously). The priority decides, which client (the one with the highest number) will receive incoming messages; sending is still possible from all clients you are logged on with.
After clicking the button "Register new user", the account creation should be confirmed (or you will be told that e.g. the username is already taken). Once your account is created, you are ready to chat!
Here you can see an example of services that are available on a server:
Note that you can usually use services on any server, not especially those you have an account on.