I hadn't thought to test this in the past and may have missed it being brought up before: When passwords are changed in the Android app (4.5.2b2 and, apparently, before), the old password isn't saved to Previously Used Passwords. I've checked on my Mac and found that this was the case in several instances where passwords were changed on the phone app. My vote would be to save the old password to the database so that it could at least be available on a Mac or Windows computer even if it couldn't be directly accessed from Android.
1Password Version: 4.5.2b2
Extension Version: Not Provided
OS Version: Android 4.4.2
Sync Type: Dropbox