I had the same issue and found that the problem for me was the gradle version in the project configuration. It was set to Default and when I set it to the gradle version I was pointing to in the plugin configuration in the Manage Jenkins > Configuration Options, It found gradle and worked properly.
This is a difficult issue to debug and I hope this saves someone else some time.