Authentication failed even though all the correct information entered

I’ve set up the plugin just as explained. I’ve got my Developer Test Key, Test Account Number and
Test Meter Number, and also I’ve got an email with my Web Services Password.
Still, when I try to buy on my website, I am getting this information: There are no shipping methods available. Please ensure that your address has been entered correctly, or contact us if you need any help.
I’ve enabled Debug mode, and this is the problem:
[Severity] => ERROR
[Source] => prof
[Code] => 1000
[Message] => Authentication Failed
I’m aware that this means that I haven’t entered correct information when setting up the plugin, but I’ve tried many times, and those are the only account information I’ve got. I have found on your website screenshots of how to know what information goes to what field in plugin settings, and I’ve done it right.
My shop is shipping from Denmark, and I’ve tried to put some US address to checkout, and also I’ve tried with Danish address, but I’m getting the same message.
I am using basic, free version of the plugin.
So, can you please help me solve this problem? I’m working on this for a few days, and I’m pretty tired and helpless.