Try forcing your phone to Look for Bluetooth Devices:

Menu->Settings & Tools->Connections->Bluetooth->Handsfree->[Look For Devices]

I can't remember what position I had to have my inginiton in, but it worked like a charm. It sure beat trying to figure out the manual (which seemed to be incorrect for my setup).