I have been using MACs since 1991, so I stuck with the fight to sort my bluetooth problem and 3 hours in store over 2 days, by default I think I have found the problem... or more impotrantly, a solution.
My phone was replaced yesterday because the BT apparently would not work. The new phone did the same! Went back and finally found a genius who could get the BT to work the personal hotspot from a macbook pro using bluetooth (pair them, then use the bluetooth icon at the top of the screen to connect). Had the phone completely reset during this, so had to go back home to reload / restore the backup, but we notice the cleared and reset phone actually worked perfectly with the car's bluetooth hands free, once paired. I restored everything ftom my backup and hey presto, immediatley back to the old tricks of dropping the BT connection after 40-45 seconds, every single time...
So either an app or a stored preferance or something in the backup, don't yet know what, is corrupting the Bluetooth function. Its not iOS5.01 or 5.1 and its not the hardware, even works with wifi on at the same time...
The Solution - CLEAR AND RESET AS A NEW PHONE - ABSOLUTELY DO NOT RESTORE FROM YOUR BACKUP. I added email (exchange and iCloud + an imap account) as new accounts. Synched contacts and calender through iCloud (as a new phone). Gave the phone a new name and synched it as a new phone NOT USING THE RESTORE OPTION in iTunes. I turned off the synch apps tick box, then checking and transferring a few essentials only at a time by marking the ones I wanted to transfer and only then doing a synch. I tested the iP4 with the cars BT after each small batch of Apps had been transferred. All I really needed worked. I have avoided for the moment anything with a coms element like Skype, bump,etc not from Apple. I then created a new iTunes playlist and synched with that.
So far it all works...
So having had it suggested it was Land Rover / Ford kit - to needing to replace my car everytime Apple does an upgrade - to having geniuses on Apple's online service refuse to recognise the problem and leaving us dangling until we get cut off (withour then returning the call!), the store guys didn't find the glich, but they shore as **** tried and by a process of elimination.... we got to a solution.
BTW Check your manual / manufacturers web site, because it appears to be better to pair by initiaiting the process from the bluetooth equipment, rather from the iP4, in some cases.
Hope it works for you and if you find the culprit App or setting that has caused you the problem, please post it here and tell Apple!
Good luck.