Manglende kompatibilitet mellem Toyota Touch&Go og Nokia E5-00 telefon via Bluetooth

Hej.
Har lige anskaffet mig en sprit ny Toyota Avensis med Toyota Touch&Go installeret. Forventede, at det virkede med min Nokia E5-00 telefon, eftersom den er på Toyotas liste over kompatible telefoner (http://www.toyota-europe.com/own/bluetooth/bluetooth_connect.tmex), og det virkede da også fint, da jeg var ude og prøve bilen.
Sagen er imidlertid, at telefonen godt nok danner par med bilen, og den kobler sig på bilens system og fungerer fint, indtil bilen slukkes. Bluetooth kobles fra, og der høres et tydeligt klik fra telefonen. Og telefonen fungerer fra dens håndsæt. Men når bilen startes igen, kan Toyota Touch&Go ikke se telefonen igen. "Forbindelsen er tabt" skriver den. Og selv om jeg forsøger manuelt at koble den på, er det ikke muligt. Eneste mulighed er at genstarte telefonen. Så finder bilen telefonen igen uden problem.
Med det kan vel ikke være rigtigt, at det skal være sådan? Eller?
Touch&Go firmware er nyeste version 1.71.3L,
Nokia firmware er nyeste version 071.003.

PS. Har prøvet med hhv. Apple iPhone3 og 4S, og de virker begge upåklageligt.