I can only speak for Firefox 3.6 on Windows 7 (not compatible w/ Ubuntu unfortunately), but after installing voice and video chat, go into:
Tools > Add-ons > Plugins then enable the Google Talk Plugin which for some reason is disabled upon install. After you enable it, go ahead and restart the browser then video chat should be working for you.

