I had this issue too with my cars hands free system. When setting it up my phone said paired but not connected and I had to make it discoverable to make it connect again. After giving up the next day I noticed it connected. The only change I had made was I turned off the phone overnight.
Maybe a simple power cycle would work? I also manage my bluetooth connection with ToogleBlu from the app market. Hope this helps.