Washington Post: Skype has updated its iPhone app and now supports video calling over both 3G and WiFi. Apple's Facetime also offers video calling, but only over WiFi.
However, the new app does have some drawbacks. The picture quality is quite grainy, and it eats up a lot of bandwidth. It burns through about 3.2 MB per minute.