This looks pretty nice: A GPL IM client based on Gaim that lets you make VoIP calls direct to all your IM buddies (even on different networks) - see:
See also the following page for a link to the source code: http://www.linspire.com/lindows_products_details.php?id=12646&pg=specs
I don' t know if there's a package already in Debian for this, but you can certainly get binaries for Linspire which is Debian-based. It'd be good to get this in universe for Ubuntu if possible.
I've always been a bit skeptical about Skype and if this works as advertised it looks like a better system since you can migrate all your existing buddies.