Google Play International Purchases Receive [InvalidClient] Error

We have an app on Google Play called Pork Chop Hero (try it out!). All our in-app purchase stuff seems to work fine during our testing, and we have a couple purchases recorded for the United States. However, it seems anytime an international customer tries to make a purchase, they receive the dreaded InvalidClient error and the purchase fails.

Given that InvalidClient can mean a bunch of different things, none of them seemingly applicable, we are at a loss for what’s going on.

Has anyone else experienced this behavior or have any hints about what it could be?

Half the problem is that we can’t really test internationally.