How does the Amazon Appstore verify its apps?
According to their dev blog, the appstore does download a small token for DRM'd apps which it uses to validate them at launch:


  How can you verify that the user has an entitlement to the app without internet access?
  
  During the installation process for an
  app, the Amazon Appstore client
  downloads a small token that grants
  the user the right to access the
  application. A valid token permits the
  user that purchased the app to access
  their app offline. The Amazon Appstore
  client will periodically communicate
  with Amazon servers to refresh the
  token.


My guess as to why you see the error is that the token is either out of date or just got corrupted somehow (bug in the appstore maybe). Re-downloading probably refreshes the token since it's originally retrieved at install time, but it sounds like you may also be able to clear the appstore data and sign in to get a valid token, or possibly just launch the appstore and let it connect/refresh itself (haven't tried these myself as I haven't had this error yet).