I did all that. Multiple times. I get "Pairing failed. Authentication time-out. Try again?" every damn time.

I can successfully pair to everything else I've tried, including four different computers. It only fails with the N800.