I hadn't had any issues with either Pidgin
since the minor
issue back in January.
However, as of yesterday, ICQ was refusing to work on Pidgin.
Seemingly there was a new release of Pidgin (2.5.5), however Ubuntu hadn't released a packaged version.
Since Pidgin is open source and they release the source files it is possible for a user to create their own Ubuntu / Debian package (.deb), however I don't like doing that unless I really really have to.
Fortunately there are other people out there who are more than capable of packaging files, so you can get a working set of .deb files here.
In order to install the new version of Pidgin you will need to remove the old one first. You won't lose your configuration settings by removing the old version (unless you purge it completely). You can probably do that via the UI, however it's just as easy to do it from the command line as root:
apt-get remove pidgin
Download all the .deb files from the site I linked to above and install each of them using:
dpkg -i filename.deb
The last one you install should be pidgin itself (the version I got was pidgin_2.5.5-1~getdeb1_i386.deb), so the command would be:
dpkg -i pidgin_2.5.5-1~getdeb1_i386.deb
It seems to be working fine now, so I'm happy.