Membership plugin not accepting any Usernames

I've set up the Membership plugin at my site You can see the various subscribtions here:

My problem is that the system is not approving ANY new Usernames. It says that the username is not valid. (I've already translated it to Norwegian, so I don't remenber the exact wording...)

Any ideas why?