Get an Android 4.2 device, sync with Traveler, use for a few hours, and the problem will reliably appear.
The change is due to the multi-user support newly added to Android 4.2, which allows users to share a tablet device but have separate profiles.
Apps need to be aware of this new structure (probably new on device storage structure) and work within the new framework to support storing credentials. Amazon just updated their appStore app to support this, as their app experienced similar issues.
Feedback response number WEBB92DR4S created by Lawrence Micallef on 11/25/2012