That can also happen if you change the name of your device. It will still be advertising a key that other radios recognize from earlier, but with the wrong name.
But you should definitely update your firmware, as meh suggested. All versions from 2.6.11 on can recognize and warn you about potentially compromised keys.
It sounds like you may actually have a compromised key. There are going to be a fair number of those around, because of the "bug" (really more of an oversight) in the pre-2.6.11 firmware. I had to get new keys on one of my radios too. Just make sure you're running 2.6.11 or later before you generate new keys.
I don't think your keys affect your interactions with the default public channel, although I could be wrong.
What I would do is perform a factory reset on the radio and set it back up from scratch. It doesn't take that long to do and it should eliminate any configuration problems that have crept in from multiple updates.