Dear Adam,
What version of GnuPG are you using? This doesn't look like a python-gnupg problem, as it doesn't control the actual generation of the signature. If all else fails, turn on logging, and see the commands that python-gnupg uses under the hood to invoke gpg. If you get the same failure calling those lines directly from a terminal prompt, then there might be some problem with your gpg installation. If it succeeds, then run the test file which comes with the source distribution (test_gnupg.py). If it fails, post the results.
Regards,
Vinay Sajip