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!).

Then

1
$ sudo apt-get update && sudo apt-get dist-upgrade

You'll see something like:

1
2
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.