do you know if it's the receiver sattelite lock or bluetooth link that takes time to establish? Has it ever worked quickly?
I've got a BT receiver - http://www.qstarz.com/products/bt-q880.aspx - and Tomtom 5 on a PDA. Mine locks within 30-45 seconds from switch-on generally, and it's got indicators on the receiver to show status of internal sattelite lock and bluetooth link integrity, so it's easy to see which is holding the system up if it's slow..