Careful with posting keys to a public forum – I’ve replaced them with placeholders.
There are times when an application record can get in a state where it falls out of a cache, but it doesn’t happen very often.
That said, I think I know what is probably your issue – are you using callback-based OAuth 1.0A? As in does your Android SDK make use of a custom URI scheme and pass a value to oauth_callback on the request token step?
If you look at the 401 error you’re getting in that step (the body of the response) you’ll likely see a hint to your problem:
“Desktop applications only support the oauth_callback value ‘oob’”
If you want to use callback-based OAuth, you need to put a placeholder URL in the callback URL field on your application record.