I'm running Lucid and had all of my GPG keys disappear from Software Sources, Synaptic, Update Manager, etc. The result was a string of error messages similar to what you've described. So, in case it's the same problem...
Further investigation led to it being caused by an error in libreadline.so.6 which caused a parsing error in GPG.
Further investigation (and comparison with a working system) showed a copy of libreadline.so.6 in /usr/local/lib. There are also linked copies in /usr/lib/ and /lib. I have no idea how the extra copy got into /usr/local/lib. It wasn't the same as the others.
The solution was to delete /usr/local/lib/libreadline.so.6 and replace it with a link to /lib/libreadline.so.6.
After that, all my links to GPG keys reappeared under the "authentication" tabs and the error messages stopped.