Today I expirienced the issue, that
empathy (the ubuntu icq, msn, facebook, ... client) was not able to connect to ICQ anymore.
To fix that issue, just install pidgin ppa (yes, I know you want empathy, but you'll need libpurple to fix it for empathy!).
$ sudo apt-get update && sudo apt-get dist-upgrade
You'll see something like:
Configuring libpurple-bin ein (1:2.7.5-1ubuntu2+pidgin1.10.10) ... Configuring libpurple0 ein (1:2.7.5-1ubuntu2+pidgin1.10.10) ...
and everything is fine again. Just restart empathy!
Thanks to twenty-three for the hint.