It looks like that telepathy-haze is using libpurple's client key and that key is now blocked from ICQ servers. After changing it with client key used by pidgin, it's working again.

If you want to test it, you can try my libpurple package: http://www.filesonic.com/file/1218158274

a here is a patch that I applied to source code: http://pastebin.com/E4zheP10