the new firmware does a better job of generating keys, and now waits until after the radio region is set by a user. wiping and reflashing recreates the keys it got when a vender bulk flashed devices.
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.
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.
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.