Linux debian unstable
using gnome, gpg, seahorse and evolution the key verifying process does not work, since the keys are not submitted in hexadecimal format i.e. with 0x before the key. The keyservers I tested (e.g.http://www.dfn-pca.de/pgpkserv/) require this format.
How To Repeat
Take a key, try using the form without 0x at http://www.dfn-pca.de/pgpkserv/ and try with 0x.
The keys which were submitted via gpg obviously lacked the 0x