Skype works fine with both voice chat and video chat as long as the drivers are properly installed (google your drivers if there's a problem). Get it from Medibuntu which stands for Multimedia, Entertainment & Distractions In Ubuntu. Configure the sound devices(skype test as well) and video devices if the default doesn't work(Ctrl+O or Skype Menu==>Options) and don't forget to unmute the microphone. (Look at the images bellow).
Empathy which is almost like Pidgin but what it lacks it good looks and the integration with gnome notification(Pidgin works great with it). It will be the new default IM for Ubuntu 9.10 Karmic Koala but that doesn't mean you can't install Pidgin. Just download Pidgin or search it in the Synaptic Manager. Install Empathy from Synaptic Manager(Make sure you install Telepathy as well). Voice and video chat enabled and all you have to do is click on the microphone or webcam icon next to a contact in your list.
NB: Do remember that voice and video chat only works for Gtalk accounts on both Pidgin and Empathy.