Like I said to someone else, the real answer is to not sign documents that are wrong. To avoid doing this, you might have to be more precise than "my public key is X." You probably should include a timestamp, an expiration for the key, a hash of the previous message so people can tell what is supposed to supercede what, etc.

That way, if people get multiple messages from you, they can actually verify which one is supposed to be the most recent and what your key actually should be.

That will solve your problems and let you disseminate public keys through Twitter.