I thought this might be a problem since the Skype web site only supports 32 bit versions and also only up to 8.04. However, doing a search around the ubuntu forums shows that skype can actually be installed directly via Medibuntu!
1) Install medibuntu
2) Get "getlibs"
3) Now simply enter the following two commands:
sudo getlibs -p bluez-alsa
sudo apt-get install skype
It will then magically appear under "Applications>Internet"
I had to change my skype settings in order for the microphone to work
I needed to change it to "HDA Intel (hw:Intel,0)" for the mic to work and I had to change "Sound Out" and "Ringing" to "pulse".