Ok so now I have tried just about everything I can think of.
I have reset my password to Skype.
I have tried Skype on my PC and logged in on Skype's web page (OK).
I have written my password in a normal textbox just to make sure I typed it correctly and from there copy-pasted it. Web page login from the N900 works but not working in N900's IM accounts setup.