I forgot to mention one thing I also did. I deleted the Skype account from my N900 and tried setting it up again. Just in case there were any corrupted files, settings with my previous N900 Skype setup. I also cannot see the connection between phone number format and the fact that I can't login to Skype.