Signature verification, Android in application billing after unsuccessful work

Background:

We have an Android app that is currently being sold through Google Play. For the application to function, the user must purchase a "token" through In-App Billing. "Token" is a consumable item, for example, once and ends. To validate the token, we send the purchase data to a server that uses standard Java RSA security code to verify that the information returned from the Play Store is valid. (Code below). Before releasing the app, we did extensive testing, and even after the app was in the store, we ran a few more tests. The data returned from Google is validated every time. Then around the beginning of December, the signature verification started to fail. We have not changed the code or application in the store, and the verification code on the server remains static.

I was debugging the code and running the receipt data and signature data that was returned from the Play Store and that doesn't really complete the verification. I am at a loss to explain what changed, or why validation started to fail when it works fine.

Question:

Has anyone come across this before when signature verification fails in an app that hasn't changed? Any clues on where to start looking to try and figure out where problems might arise?

Additional Information

The only thing I can think of changing is Google that released the in-app billing API v3, but this shouldn't affect V2, which is what we are using.

For AID development, we use net.robotmedia.billing library to handle IAB.

Below is the server confirmation code for the data returned from the Play Store

where encodePublicKey => our public key from the Play Store

signedData => base64 encoded receiptData as return from Play Store purchase

signature => returned to Play Store

public class Security {

    public final static Logger logger = Logger.getLogger(Security.class.getName());

    private static final String KEY_FACTORY_ALGORITHM = "RSA";
    private static final String SIGNATURE_ALGORITHM = "SHA1withRSA";

    /**
     * Generates a PublicKey instance from a string containing the
     * Base64-encoded public key.
     * 
     * @param encodedPublicKey
     *            Base64-encoded public key
     * @throws IllegalArgumentException
     *             if encodedPublicKey is invalid
     */
    public static PublicKey generatePublicKey(String encodedPublicKey) {
        try {
            byte[] decodedKey = Base64.decode(encodedPublicKey);
            KeyFactory keyFactory = KeyFactory.getInstance(KEY_FACTORY_ALGORITHM);
            return keyFactory.generatePublic(new X509EncodedKeySpec(decodedKey));
        }
        catch (NoSuchAlgorithmException e) {
            throw new RuntimeException(e);
        }
        catch (InvalidKeySpecException e) {
            logger.error("Invalid key specification.", e);
            throw new IllegalArgumentException(e);
        }
        catch (Base64DecoderException e) {
            logger.error("Base64 decoding failed.", e);
            throw new IllegalArgumentException(e);
        }
    }

    /**
     * Verifies that the signature from the server matches the computed
     * signature on the data. Returns true if the data is correctly signed.
     * 
     * @param publicKey
     *            public key associated with the developer account
     * @param signedData
     *            signed data from server
     * @param signature
     *            server signature
     * @return true if the data and signature match
     */
    public static boolean verify(PublicKey publicKey, String signedData, String signature) {
        Signature sig;
        try {
            sig = Signature.getInstance(SIGNATURE_ALGORITHM);
            sig.initVerify(publicKey);
            sig.update(signedData.getBytes());
            byte[] decodedSig = Base64.decode(signature);
            if (!sig.verify(decodedSig)) {
                logger.error("Signature verification failed.");
                return false;
            }
            return true;
        }
        catch (NoSuchAlgorithmException e) {
            logger.error("NoSuchAlgorithmException.");
        }
        catch (InvalidKeyException e) {
            logger.error("Invalid key specification.");
        }
        catch (SignatureException e) {
            logger.error("Signature exception.");
        }
        catch (Base64DecoderException e) {
            logger.error("Base64 decoding failed.");
        }
        return false;
    }

}