Comment 1 for bug 420813

If your keys are being blacklisted, then, well ... they may appear to be working just fine, but everyone else on the planet can get the corresponding private keys with only a little bit of effort! You really do need to regenerate those keys. Any release of Ubuntu that's still within its support lifetime and that has all security updates applied will be fine. I'm afraid that I regard the security risk here as several orders of magnitude more serious than the inconvenience of needing to regenerate keys.

Whatever that signing failure is, it's unrelated to the blacklisting; it could easily be a configuration error due to confusion among multiple keys, or something. If you'd like to file that separately, with as much debugging information as possible, we can look into that.

See:

  http://www.ubuntu.com/usn/usn-612-2