I am having the same problem on my Droid with Android 2.01. The phone is paired with my BMW. It used to connect as soon as I started it up, but nowadays it often doesn't connect at all unless I power cycle the phone. I downloaded a widget that turns BT on and off, and if I toggle it, it will usually connect.
One day I was on a long drive and I was wondering if maybe it was just taking a long time, so I left it alone, and once a call came in it finally connected.