Solved
Solved the problem with my Prius. This is what I did:
1. In your phone, Go to the settings, Bluetooth and click on the (i) of your car's Bluetooth. In my case it was CAR MULTIMEDIA. Then click on Forget this Device.
2. Turn off Bluetooth in your phone so that it doesn't try to connect to the car's BT again
3. Go to your car, turn it on and delete your phone from the BT settings of your car and reset all BT settings to Default
4. In my Prius you have to delete the phone twice, because there's two BT connections, one for audio (multimedia/music) streaming and another one for phone Bluetooth (to talk on the phone). Make sure you delete both of them. It takes just a minute to do it, one is in the phone settings and the other in the audio settings.
5. Turn off your car and wait for a minute or so (this might not be necessary but I did anyway)
6. Turn your car on again.
7. Turn BT back on in your phone
8. Register your phone with your car's BT. The phone will ask you for the code (the default is 0000 or 1212).
9. That's it, once they're paired again, everything went back to normal.
Steering wheel controls are working again through Bluetooth, sound is great, and phone calling works again with no choppiness.
Hope this helps.
