We have git installed to a non-standard location that is not on the jenkins app server user's path. This isn't a problem for the core git plugin as we just specific the path in the git configuration but the Git Parameter Plugin doesn't appear to use this value when trying to run the "git" command.
https://gist.github.com/2647833 Should I file a jira issue for this?