Linphone supports video calls on Android !
We just published on the Android market a new release of linphone for android that supports video calls.
Supported codecs are mpeg4 (320x240 @ 20 fps) and H264 (QCIF @ 7 fps), based on libavcodec and x264 open source projects.
This works on phones models using an ARMv7 processor with NEON instruction set (nexus, samsung galaxy, htc desire ...).
Direct link to the apk is here for those not using the Android market application.