You might need to pull the negative terminal off of the battery. Then turn your steering lock to lock, put your windows down and then hold the up buttons for 5 seconds after they have closed and then try pairing the phone to the car again. My 2010 car was very unstable when I first got it but the more you use it the better it seems to get. I haven't done any Blue and Me upgrades and it works fine with everything but the text reader no matter what phone I use.
I've a 930, my wife has a 950XL and previously a 925... all of them worked straight away with the uConnect.
The process is easier if you start the pairing from the uConnect side: press "Phone", then "Add new phone", and it should pick it up straight away. Actually, if there's no phone paired, it guides you through the process as soon as you press "Phone".
If you've already power-cycled your phone (switch it off, remove battery for 10 sec, re-insert battery and restart), then the next thing is to reset the uConnect. Press down the left ("Volume/Power") and right ("Browse/Enter") knobs for 5-10 seconds to reset the unit. Then try to pair the phone again.
I'm not sure if this wipes your stored radio stations, and navigation favourites (if it's a nav), though.