I got Skype to work with video on my Droid Bionic by doing the following:
1 Uninstall all Skype versions on your phone.
2 Install the modified version of Skype found here xda-developers - View Single Post - Skype 18.104.22.168 (v11) / fixes, extra features & more!
3 Sign in to Skype and on the main page hit the menu key (on your phone) then go to Advanced Settings.
4 Check-mark the option Use valid preview surface
5 Once back and on the Skype main screen hit the menu key (on your phone) and go in to Settings (Regular Settings this time) and check-mark Enable video calling
Enjoy your video calls on your phone.
I have tested this on mine and it works Phone to Phone or Phone to PC. Both cameras are working.
Credits go to theos0o from XDA developers and gazan1204 from droid forums