Just tried it.
Made a Skype video call using the "Fring" app for Android on my Nexus One (Android v2.2 pre-release) to another Skype account on my desktop - over 3G.
Both video feeds worked perfectly at both ends.
So yes, Skype video calling works fine over 3G with the "Fring" app on Android (and probably any other platform Fring supports - if allowed to).
I tried this because I was curious to see how it works (very well) and because I heard that iPhone 4's "Facetime" only works on WiFi.
Hopefully Skype and Fring on iPhone aren't similarly restricted.