I have a Pixel 10, updated to Android 16 on Sept 5th, have not had any issues with BT or messaging.
Don't know if it makes any difference, but I only received the new phone in late Aug/early Sept timeframe, so I had to go through the whole pairing process of connecting a new phone to car, and it's possible that when I first paired them I was already on Android 16. Might be painful, but you could try disconnecting your phone from the PS App & car, then starting over the pairing process like it was a new phone.