FWIW, Salut/Bonjour works fine for this on Windows, Mac, Linux, iPhone and Android.

Serverless chat. Automatic announcement of status and others. There's already a telepathy plugin for it and I've been using it for quite some time.

Most distribution support it right out of the box, Ubuntu has it in the regular chat section, iChat supports it and there are numerous Windows, Android and iOS Bonjour/Salut clients.