Removing the package pulseaudio also did the trick for me. For any new users the command to use is:
sudo apt-get remove pulseaudio
and then restart skype and it worked straight away
----------------------EDIT-----------------------------------
As myself and other users discovered this is NOT a good idea. If you do this you probably won't be able to log in to Ubuntu after. If you have experienced this problem you can fix it by hitting CTRL+ALT+F5 - type your login and pass and reinstall pulse audio by entering:
sudo apt-get install pulseaudio
hitting enter and then flick back to your normal login screen by using CTRL+ALT+F7.
Like krazykookmany setting the devices under skype to use pulse is a much better idea, and also fixed my problem... Without breaking my OS.
Bookmarks