Do you have Broadcom Bluetooth software installed on your machine? If so, try disabling or uninstalling it. It's been reported to have caused the same problem you're having by other users.
In Skype go to Tools -> Options -> Advanced settings. At the bottom of the screen click on “Manage other programs’ access to Skype”. Do you see any applications listed there?
Disable Bluetooth, or remove it, from that Advanced setting and that may correct your problem.