I had this problem aswell. Nothing seemed to help - I deleted the account, created it again, rebooted...

Finally I used my other account, just changed the username and password, and was able to login. Then I logged out and changed back the original account details and now Skype is working again.

Clearly a bug, but seems to be easy to go around.