Sorry about this but I don't have a clue when it comes to this sort of thing........but why won't my Bluetooth on my phone pair with the Bluetooth on my nexus 7 tablet?
Don't know but I can say my mobile would not connect to my PC last night. However the PC did spot I'd plugged the Bluetooth dongle in and tried to load the drivers (something it ought not need to have done since it's been used before) and failed to load them all.
Maybe your issue is similar, that you need the drivers loaded, maybe ?
You may have to make both devices discoverable before attempting pairing.
Try searching for devices from the Nexus to phone instead of phone to tablet and remember to allow for auto connect when paired successfully. :)