I had a similar problem with my 6310i. One thing to check is that you don't have lots of SMS messages stored on your phone - if you do, dlete as many as you can. It's as if the phone cannot transfer the messages to the car quickly enough during the pairing process before it times out. Once I dleted a load of messages it paired reliably.
One other thing is that I did have a faulty centre cradle, but this thing with the messages is real - lots of similar reports of this problem in the UK.

Hope it helps,

Petert