Call your old boss immediately and see if your old job is still available. You currently work for a bad company who cannot do basic tasks like background checks correctly.
Did they elaborate on what the problem with the background check was? You don’t have to tell us, but if you don’t know of anything that would raise a red flag it’s worth asking some clarifying questions.
If you want to try and keep your job, Go to your boss and let them go to bat for you. You said you’d already passed the background check, so something is up. Let your new boss guide you on this. Cc any communication with HR to your personal email.
If you have an idea of why you failed the background check, adding that information would help. Less information = less helpful answer. Change your screen-name if you want, but more info = better.
No matter what I'd you did everything right by checking before turning in notice.
In retrospect you should have asked explicitly if the background check had comeback. They may also be incompetent, and would have told you it was completed when it wasn't (and yes, I've seen this happen).
I'm also assuming you filled out the background check forms accurately to the best of your knowledge. If you have something like a DUI on your record we can tailor our answer for that. If you're genuinely in the dark, then that would be a completely different answer.