I was asked to change my password, because of suspicious activity. Having done that, my blogs are now deleted!
With hacked Blogger / Google accounts, causing deleted blogs, there's not a lot of advice that we can provide.
As you just discovered, the account is recovered almost immediately. Blog recovery, unfortunately, takes longer - sometimes, 1 to 2 days. You'll have to wait, patiently, until your blogs are verified by Google Security staff.
We're also seeing the normal amount of reports of blogs deleted by Blogger, when detected for malware, porn, or spam. In some cases, blog review ends with the conclusion that the blog was not, in fact, deleted for a TOS violation. In these cases, the blog won't be restored by Blogger Support.
In some cases, blog review - which starts with a claim of spurious classification for malware, porn, or spam hosting - ends with advice to have the owning Blogger / Google account recovered.
The blog owner has to wait until the review process is complete, to learn where he should have started, days ago. As I've observed a few times in the past, anonymity - whether intention or accidental - can cause problems with blog ownership. If your Blogger / Google account is locked, but you don't get the required notification, you can waste valuable time with the blog offline.
Whether you intentionally anonymise yourself - or accidentally create a second (or third) Blogger account, you may not get essential email from Google, advising you to recover your account. When that happens, your blog will stay offline until it can be reviewed - and review starts only after you recover the account that was locked.
Now, you're going to have to open every possible email account, and carefully look for the overlooked email. If you never find the missing email message, you're going to have to login to Blogger, using every possible email address that you may have ever used, until you hit the locked Blogger account.
When you do identify the locked account, you'll get the advice to change your password, solve a CAPTCHA, and / or answer a number of secret questions, to prove that you are the account owner. Or, if you're lucky, you can await a phone call (digital or voice) with a special code, to unlock your account. Either way, you'll be unlocking the account while under stress, with the blog offline.
And after you get the account unlocked, you'll still have to wait until the blog(s) can be verified.
If you try to blame Google, for this disaster
Why was my blog deleted? I did not spam!you will simply be wasting your time. This is yet one more story that starts with gratuitous and uncontrolled creation of multiple Blogger accounts and email addresses.