I had some problems to get Skype video working on my Debian amd64 system.
The problems are grounded in the outdated Skype-Linux-Beta.
They offer some amd64 packages but those are contain i386 libs.
Skype-video still uses Video4Linux1 although Video4Linux2 is available since the 2.5.* kernels!
To get things working you need to use the 32bit v4l1 compatibility library:
sudo apt-get install lib32v4l-0