General :: LVL Check Timed Out?

I'm using Google's LVL mechanism for licensing in my application and in the last few days I've started getting reports from users that the licensing mechanism fails. I get the following lines in the log from those users:

Code:
Line 925: 03-26 23:04:41.463 I/LicenseChecker(31875): Binding to licensing service.
Line 926: 03-26 23:04:41.473 I/LicenseChecker(31875): Calling checkLicense on service for com.blabla.myApp
Line 927: 03-26 23:04:41.473 I/LicenseChecker(31875): Start monitoring timeout.
Line 930: 03-26 23:04:51.472 I/LicenseChecker(31875): Check timed out.

I've made sure with the users that they have Internet connection, you can see that it takes ~10 minutes before I get a timeout so this isn't just a momentary thing, and on top of this, I check for license several times before deciding that this is invalid.