I still in the testing mode of an Authorize.net setup and am receiving this same error message. I configured it by using the link posted above by DrByte, but as it said the MD5 Hash was OPTIONAL, I skipped it at first.

As I received the exact error message described by euroxtreme I decided to add that security, but I still get the error. Any other hints? I don't want to take it out of Test Mode until I'm sure a user won't get that error.