I just got a new iPhone 5c from Verizon. When I tried to connect it to my 2008 Prius, the screen on my car says the connection failed, even though I had the Bluetooth enabled on my phone. My phone's screen says it's searching, but no connection made. I had a cheap Android phone before and it connected right away.
@Keri Weeg, don't forget to come back and let us know whether this worked. If it didn't, let us know what did. Thanks.