The problem is that the plugin tries to use the OpenID team memberships extension, which isn't part of the Google OpenID implementation. Google must have recently started limiting the URL that gets passed during the OpenID flow or our list of people in our authentication list got too big. Either way, the query string is enormous and the way to fix it is to disable this extension.
To fix this issue, you have to download this patch and apply it to the current OpenID v1.7 branch. I tried commenting out the offending code, but tests within this plugin started to break and prevent you from building the .hpi plugin.
1. git clone https://github.com/jenkinsci/openid-plugin
2. wget https://github.com/jenkinsci/openid-plugin/pull/4.diff
3. patch -p1 < 4.diff
4. mvn package
Recompile the OpenID plugin and copy the target/openid.hpi plugin into your jenkins/plugins dir. Restart Jenkins and the problem should be gone.
We're hoping this commit gets merged soon!
Update (1/16/2014): Add the disable statement in your /etc/default/jenkins file with the JAVA_ARGS variable. Because Java system properties must be defined before .jar files are included, declaring them with JENKINS_ARGS will not work.
JAVA_ARGS="-Dhudson.plugins.openid.impl.TeamsExtensiondisable=true" JENKINS_ARGS="--webroot=/var/cache/jenkins/war --httpPort=$HTTP_PORT --ajp13Port=$AJP_PORT"