Thanks, much better. I was still on version 0.9.4.
Ugh. I didn’t even realize this mess existed. (Feel free to skip these links:)
Email Overview
GPG keyservers from within Whonix workstation - #7 by tempest
Most Whonix users use GPG through the command line or via the KGPG frontend (interface). Tempest’s guide walks you through “patching” TorBirdy so it will work seamlessly with Whonix. I don’t know which is more difficult: patching TorBirdy or learning to use another GPG interface. Like I said at the beginning, they all interact with the same backend system, GPG. In any case, it might be helpful to learn the other options since there will be times when you will want to use GPG without having Icedove available / configured properly.
For the guide, I tried it myself and it worked fine. Since you were able to use gpg from the cmd line, we can rule out network connectivity or keyserver issues. Most likely, you made a typo! 
Start Icedove, go to Add-Ons, disable TorBirdy. Close Icedove.
cd ~/Downloads
rm torbirdy-current.xpi
Start again from Step 3. Copy/paste commands whenever possible. Make sure ‘//’ is at the beginning, in front of the double-quote.
Start Icedove, go to Add-Ons, Install from File. Close Icedove
Restart Icedove and try search again. You can search for “anonguide” instead of the big number (fingerprint).
After all that, if it still doesn’t work, re-install a clean torbirdy and use KGPG (in your KDE menu, Utilities).
Also, please accept my apologies… You were in the right place after all! Not a GPG issue - it’s a Whonix issue 