If you simply want to have a voice conversation with another person
over the internet and if you have no preferences on the underlying
protocol, then I say simply to use Skype which is easly available on
www.skype.com for both windows and linux (.deb package available too),
and lets you talk for free with other skype users.
Ah, I should have mentioned this. I am specifically looking for something that
is *not* Skype, because (a) Skype has no ALSA support and very bad OSS support,
making it a chore to use, and (b) it cannot be installed alongside KDE 3.4,
which I plan to dist-upgrade to soon (I'm holding back until amarok is
installable).