I have an Apple push services certificate due to expire in 2 days so I created a new one but have the same issue as listed above where the new certificate is not trusted and the root certificate is not found. I have followed and tried many of the steps already listed above, but none have worked. All other certificates in my keychain are shown as valid. I am at a loss now as to what I can try next.

I'm having the same problem. I have MacOS Big Sur 11.6.7 on a MacBook pro Retina late 2013 and have Xcode 13.2.1 installed and can't side load to my device anymore iPhone 7 with iOS 15.5. This is making my development and testing a real problem as my device and MacBook are both serving me well and I am reluctant to upgrade just to have the ability to side load. Come on Apple keep up the compatibility so we can continue to develop apps for the App Store.