do you see if the key is also disabled ?
see if you can synchronize the key with PGP GLobal Directory or any other keyserver which you are using.
check the below KB:
Public Keys become disabled in PGP Desktop
http://www.symantec.com/docs/TECH149041
also try to submit your key to Global Directory where you will be able to verify your key and then download again from global directory and import to PGP Desktop again. See if this trick helps.
HOW TO: Upload a key to the PGP Global Directory (Windows)
http://www.symantec.com/docs/HOWTO42020
check also this thread if it can be of any help but looking from your post most probably not ?
https://www-secure.symantec.com/connect/forums/pgp-cannot-get-my-keys-verified-nor-trust-level-changed-implicit
HTH