Since upgrading my work machine to karmic koala, I've noticed that my sound had stopped working. There were some broken packages in aptitude and Skype knew there was a problem as it notified me when I tried to make a call. I saw some issues reported with karmic, notably this one, so I uninstalled pulseaudio

sudo aptitude remove pulseaudio

When I restarted Skype, everything seemed to work as expected - for reference I have a thinkpad T400, if you're having the same issues, then hopefully this will help!