I just installed Skype on my Ubuntu 12.04 again and somehow I can only login if I start Skype via root (sudo skype) in the terminal. If I try otherwise via dash or just "skype" without sudo permission I can't log in, it says "Login failed" or "Sign in failed" (got the German version).
Try running this command:
While replacing <your_username> with your actual username of course.
Maybe you run Skype with sudo once which, after that, root took ownership of some of the files in your skype config/history files.
If you don't need your skype logs, you can also remove your ~/.skype folder (renaming would be safer).