Was your original backup encrypted?

Did you log into your iCloud account before restoring? (I don't remember if that's a step that happens prior to restoring in the new Mac setup flow)

There could be some credential that needs to be provided in order to find/decrypt a TM Backup. If that key was not available, perhaps the OS/UI doesn't even show you the backup as a restore candidate.