I had the same problem and explicitly setting the package solved it. Similar to Aleksey’s answer, but simpler:
Intent intent = new Intent("com.android.vending.billing.InAppBillingService.BIND");
// This is the key line that fixed everything for me
intent.setPackage("com.android.vending");
getContext().bindService(intent, serviceConnection, Context.BIND_AUTO_CREATE);