My new MotoG4 Bluetooth is not connecting with my car device. My old MOTO G 1st Gen. had no problems.
It would be helpful to the community to know what the make/model of the vehicle you are trying to connect to via bluetooth on your Moto G4.
Did you ever get your Bluetooth working again? Do you know if it is just not connecting to your car specifically or is your Bluetooth completely not working (such as not turning on)?
I recommend disabling bluetooth scanning under Settings -> Location and try again.