Since it is under warranty and you have an approved phone, I would take the car to the dealer with the phone in hand. It sounds like you are doing everything right. The phone and car are seeing each other which is very positive. It could be tha that the passkey you have is wrong-- that is my bet. The dealer can read the passkey from their diagnostics computer and confirm it.

On an aside, the passkey is usually only 4 digits, and they have nothing to do with the VIN. So, if you enter the passkey, just look for and enter the four digit code.

__________________
SOLD
2000 E38 750iL Highline Edition, Upgraded with the lastest 2006 X5 Electronics
MKIV Navigation, 16:9 Display, Bluetooth, TV/Video with Backup Camera, Sirius, and Aux Input