Trouble pairing G1 (Android) with Prius BT media

I have a T-Mobile G1, unrooted, running Android 1.6. One of the first things I tried with my new 2010 Prius w/Nav was pairing it with the phone over Bluetooth. I saw that the manual says that if your device is a phone and media player, then you should pair the phone first, then the media. Fair enough.

The phone paired fine the 1st time. But when I tried the media player, it just would not pair. I tried dozens of times, called Toyota support, T-mobile support, and they both told me I was out of luck, that it would not work. I was pretty much about to give up. The T-mobile person did suggest I power down the phone, pull the battery for 10 seconds, and then power up and try again. I did this, and it still didn't work the 1st time, but then a few tries later, it finally did work. I don't know if this was due to the reboot, or what. In all, I probably tried and failed about 50 times before getting it to work.

Did anyone else have this much trouble pairing their Android-based device with the media player? My friend with an iPhone paired it and it worked just fine the 1st time!