I also get this message with a HTC Legend. It appears to be something to do with the handset since I tried another SIM with the same results, and that SIM works fine in a Sony Ericsson W660i.
Possibly a problem with HTC?? I've googled it and I only found 2 exact matches, both of which were unanswered forum questions (this being one).