The Yahoo audio problem is due to their use of the TruSpeech codec. Right now it's only a Win compatible service, or at least officially.
There is a Linux program that has some voice abilities on Yahoos servers, called Gyach Enhanced. I have been able to compile and use it on a Mandrake 9.2 system but there are some issues. I can hear eveyone fine, but when I talk it's garbled.
I installed Gyach (original) on my Mac and had it running under OS X 10.1.5, but the last version of the original never was updated with the YMSG11 login protocol...so it won't log in.
From what I can tell, the 'Gyach Enhanced' is still an ungly hack. It uses Python and GTK, but whoever programmed it was doing so for their system. If you read their docs with it, you'll see this. Especially the part about requiring the ESD Sound Daemon. I tried many times to compile it for X before noticing a big problem, they use WINE to work with Windows versions of the audio codec. So in other words there's not much use unless you have an X86 machine.