Android In App Billing "Billing service is not available on the device (answer: 3: billing is not available)"

Question

Android In App Billing "Billing service is not available on the device (answer: 3: billing is not available)"

I also built an android game that has a premium in purchasing the application, and it worked fine for me for a while. (The game was in beta testing, and users could purchase a premium upgrade.)

A few days ago, I decided to rewrite the project to clean my code a bit. Everything seemed to be working fine. (Play Game Services and AdMob Ads are still working) However, application billing no longer works. Every time the application starts, I get an error: "Billing service unavailable on device. (response: 3:Billing Unavailable)"I searched everywhere and found many people having this problem, but none of their answers helped me.

I tried:

Clearing the cache of the Google Play application and accepting the conditions when the application starts.
An attempt by several users on my phone. (All of them have been added to the list of testers in the developer console.)
Testing on at least 3 other (non-root) devices.
Double check that permission "com.android.vending.BILLING"is in my manifest file.
Using the same keystore to sign my new application.
Using the same exact namespace for my new project.
Try 3 different versions of the play store.

Here is my iabHelper code.

String base64EncodedPublicKey = "KEY HERE";

iabHelper = new IabHelper(this, base64EncodedPublicKey);
iabHelper.enableDebugLogging(true);
iabHelper.startSetup(new IabHelper.OnIabSetupFinishedListener() {
    @Override
    public void onIabSetupFinished(IabResult result) {
        if (!result.isSuccess()) {
            Log.e(TAG, "Problem setting up in-app billing: " + result.getMessage());
            return;
        }

        if (iabHelper == null) return;

        iabHelper.queryInventoryAsync(new IabHelper.QueryInventoryFinishedListener() {
            @Override
            public void onQueryInventoryFinished(IabResult result, Inventory inv) {
                if (iabHelper == null) return;

                if (result.isFailure()) {
                    Log.e(TAG, "Failed to query inventory: " + result);
                    return;
                }

                Purchase premiumPurchase = inv.getPurchase("premium");
                isPremium = (premiumPurchase != null);

                if (!premium())
                    loadInterstitial();
           }
        });
    }
});

and my onActivityResult code

I am sure that this was done incorrectly, but I do not think that this refers to this error. (This is not even called before I see the error during debugging.)

@Override
protected void onActivityResult(int requestCode, int resultCode, Intent data) {
    Log.i(TAG, "onActivityResult(" + requestCode + "," + resultCode + "," + data);

    // Pass on the activity result to the helper for handling
    if (!iabHelper.handleActivityResult(requestCode, resultCode, data)) {
        if (resultCode == GamesActivityResultCodes.RESULT_RECONNECT_REQUIRED)
            gameHelper.disconnect();
        gameHelper.onActivityResult(requestCode, resultCode, data);
        super.onActivityResult(requestCode, resultCode, data);
    } else {
        Log.i(TAG, "onActivityResult handled by IABUtil.");
    }
}