Consider the following pastebin: http://ae7.st/p/5k4. As per that pastebin, searching for the entire fingerprint returns the empty set, yet searching for the key ID, which is the last 16 digits of the fingerprint turns the correct key.
However, this is only partially. As you can see, I have two keys imported. Both have fingerprints, key IDs and other information. Yet, calling gpg.search_keys() on one key returns the key, while on another returns the empty set.
This might be two separate bugs. If so, I don't mind creating a second bug for returning one public key, but not the other.