It definitely mean someone else has your key. Me and my brothers had this problem when we were new to Blockland. We all shared one key, and when ever someone changed a name the others could not join any other server. We got the same message on our screen.
Just to make sure, I tested this on two computers.
First I got on a random server using my name Capt'n
Then going on another computer I changed my name to Test And went on to a different server.
Going back to the computer with Catp'n I got out of that server and tried to join another random server.
The same Message popped up.
Someone has your Key and changed your name.
Quick Fix -- Re-change your name, get on a server and stay there. When I changed my name to Test, Capt'n did not get kicked out of the server.
That's what I found, hope it helps. Sorry for grammar and spelling.