Same problem here, I added the source code of GoogleIdTokenVerifier to my project and changed the method:
 public boolean verify(GoogleIdToken googleIdToken) throws GeneralSecurityException, IOException {
    // check the payload
    if (!super.verify(googleIdToken)) {
      return false;
    }
    // verify signature
    for (PublicKey publicKey : publicKeys.getPublicKeys()) {
      try {
        if (googleIdToken.verifySignature(publicKey)) {
            return true;
          }
    } catch (Exception e) {
        System.err.println("Verify Token:" + e);
    }
    }
    return false;
  }
just handle the exception, the second certificate works fine.
Edit: you can subclass as Erik-z suggested if you want to make it more clean:
Edit 2: I can't make it work using the code below, I will stick to the ugly hack above.
package com.my.project.package;
import java.io.IOException;
import java.security.GeneralSecurityException;
import java.security.PublicKey;
import com.google.api.client.auth.openidconnect.IdTokenVerifier;
import com.google.api.client.googleapis.auth.oauth2.GoogleIdToken;
import com.google.api.client.googleapis.auth.oauth2.GoogleIdTokenVerifier;
import com.google.api.client.http.HttpTransport;
import com.google.api.client.json.JsonFactory;
// Remember to remove this class later by making it deprecated
@Deprecated
public class GoogleIdTokenVerifier2 extends GoogleIdTokenVerifier {
    // Add constructors as needed
    public GoogleIdTokenVerifier2(HttpTransport transport, JsonFactory jsonFactory) {
        super(transport, jsonFactory);
    }
    @Override
    public boolean verify(GoogleIdToken googleIdToken) throws GeneralSecurityException, IOException {
        // check the payload
        if (!((IdTokenVerifier)this).verify(googleIdToken)) {
            return false;
        }
        // verify signature
        for (PublicKey publicKey : getPublicKeysManager().getPublicKeys()) {
            try {
                if (googleIdToken.verifySignature(publicKey)) {
                    return true;
                }
            } catch (Exception e) {
                System.err.println("Verify Token:" + e);
            }
        }
        return false;
    }
}