Empathy and Pidgin support video and audio chats over Google Talk/Jabber/XMPP protocol. You could also give the recently launched Google Video and Voice Chat an try.
Skype also supports video and voice chat on Linux.
Or you could use Ekiga (VoIP client) for video and voice.
Gyachi has this on their web page:
This Yahoo! client for Linux operating
system supports almost all of the
features you would expect to find on
the official Windows Yahoo! client:
Voice chat, webcams, faders,
'nicknames', audibles, avatars,
display images, and more. Yet, it
remains very light-weight and
Meebo is a web service that supports voice and video chats on Linux.