I had to play with this for a while to make it work, and I don't remember the exact combination that did work; but basically:
Go to the bluetooth settings in both devices (at the same time) and turn the bluetooth off, then on, (again, both devices). This makes sure they are discoverable,and forces them to look for other discoverable devices.
When the other device shows up, tap on it and try to initiate pairing. If it doesn't work initiating from one device, try initiating it from the other. It took me several tries, and like I said, I don't remember how exactly it ended up working.