For what it's worth, I had that same error message (OS X), and I managed to fix it. After using homebrew to make sure my git was up-to-date and gpg was also installed correctly, I told git where gpg is (for some reason, despite being in my PATH, it wasn't registering?): git config --global gpg.program /usr/local/bin/gpg

After that, I had to make a tweak to gpg so I didn't get another annoying error. In ~/.gnupg/gpg.conf, adding 'no-tty' got everything working smoothly.

I agree that that was way too tedious, but it did work out. :)