Not good, i just had another user who has had one of my other apps for 2 years report that he can no longer run it, he is getting the same error. The app in this case was last updated Feb 21st.
Something seems to be going on with Google Play that is causing this for some users. How does the licensing.verify command work exactly, what would be causing this type of exception to occur?
Edit: FYI the latest user with the problem is also running Android 4.0.4, so that is the only common factor so far.