Files:scan -all shows "Catalog not found" errors after upgrading to Nextcloud 29

Upgraded how? There are multiple installation and update methods.

Also please post the exact output (you can censor our file/user names of course). And also check your Nextcloud log, post your config, apps, etc.

There is a support template which exists for a reason. It asks for all this info and more, which is needed to help you.