You're not being paranoid cakefrosting - change password on the Apple ID account, any associated emails accounts, and enable 2-factor auth if you can.
The continuing expansion of this thread is worrying and heartening at the same time - if we can keep it rolling and expanding then we can track how big this is, and hopefully send a message to the silent behemoth that is apple.
Their handling of this on an individual basis seems to be pretty good - I've seen them deactivate apple IDs, set everything straight, including financial refunds, then reactivate the Apple ID.
But with no idea of what's behind this, we don't know if these cases are all the result of concentrated and focussed brute force password cracking in Taiwan, or if there are leaks somewhere (server compromises or otherwise).
All we can do in the support community is keep this thread expanding - find anyone else and get them to post, if you can. I thought this would tail off, but it seems to keep going...