licensing returning not licensed

I am using the market licensing in my app. Recently iv been getting reports from people that after resetting the开发者_运维技巧ir phones they can install the app but when they load it. It says its not licensed. Is this Google's fault?

Its very damaging because I don't know how I can help people.

To be valid, the request must be on the same device with the same Google account.