The update json file for the gradle installer at http://mirrors.jenkins-ci.org/updates/updates/hudson.plugins.gradle.GradleInstaller.json is empty.
This means that Jenkins is unable to automatically install gradle from the gradle plugin.

Temp workaround:
Using the information from http://blog.cloudbees.com/2011/03/writing-automatic-tool-installer-for.html , we can overwrite the values in the .jenkins/updates folder, but this is only useful where we have local filesystem access. Our main Jenkins server does not have shell access, and so this is causing us some difficulties.