I have not been able to determine a pattern for this. Sometimes it doesn't pair at all, other times it pairs after 15 minutes. If it doesn't pair at all, then I can get another shot by power cycling.
evilbeef54, when you say its not pairing, has it ever paired? Have you waited a really long time to see whether it will pair? As I said, sometimes 15 minutes after drivinging, I'll suddenly get "BLUETOOTH CONNECTION SUCCESSFUL" on my car's nav screen.