If you are using gpg2 instead of gpg then git will eventually throw an error about not being able to find your key or even the gpg binary.
Just do a
git config --global gpg.program gpg2
and add the following to your gitconfig
[gpg]
program = gpg2