If I type in a different country code that the Norwegian one (which is 47), the it suddenly works.. but Im not sure I should associate my account with an incorrect phone number.. Maybe this means that Nokia Messaging is not available for Norwegians yet? >.<