Panda pop seems to be the latest app to be downloaded after Apple ID compromise - just seen nearly 10 tweets from people in the last 2 days on this. I've asked them all to take a trip over here and add their stories, if they can.
I know Apple won't respond on here, but your story is *fascinating*. I work in IT - communications tech, mainly, but I know a bit about comms protocols, databases etc. The fact that you were required to change your iCloud password (i.e. your Apple ID password - they're the same thing) looks like a dead giveaway. I've never had my own Apple ID demand I change my password, ever.
If I read that right, this means Apple knows what's going on, and they're trying to handle it (at this stage) by manipulating Apple ID accounts such that they're not locked, they just demand a password change from known devices.
In my opinion, if that's the case, it a half-arsed approach. They should just lock the accounts if they've detected what they (now?) deem suspicious behaviour. The Apple ID holder will soon notice if their account is locked and get in touch with apple direct.
Otherwise, you're still leaving the account open to abuse: if the Apple account owner is required to go to an apple store and prove their identity to unlock the account (or some other form of ID check) then security would be more assured.