Fring [Free - iTunes link] dropped us a note to let us know that with version 220.127.116.11 -- now in the App Store -- they've delivered on their promise of video calls for the iPhone.
Now, since the iPhone doesn't (yet?) have a front-facing camera, you're limited to seeing the other person on a Skype or Fring Video call using their PC webcam (or Nokia phone -- sigh, jealousy), but it's still a wondrous step towards the future.
If you give it a try, let us know how it works for you.
[Thanks to Icebike for the tip!]