Hmm, guess I'm out of ideas, sounds like a skype-specific problem then.
Maybe try reinstalling it?