Go and get some good webcam (I use the Microsoft LifeChat NX-6000), navigate to the Skype user settings

 C:\Program Files\Users\[YourWindowsProfile]\AppData\Roaming\Skype\[YourSkypeProfile]

open config.xml and follow the instruction by Phillip Torrone, seeking for the <Video> tag. I am using Skype version 3.6.0.248 and the configuration file looks quite different now. However, adding the <CaptureWidth> and <CaptureHeight> tag works fine as well with this version since it was especially introduced with version 3.6. At the end your configuration file should look similar to this one.

I re-started Skype and it looks like the other side can see me in 640×480 now.