How strange.. I just tried the whole thing again, deleted the phone from the bluetooth devices list, put the N800 in visible mode and then paired from the phone. When I went back to the N800 it listed the phone under the phones list, selected it, and then went on to try and make a connection...

It worked!

Bizarre... It's now working Nokia N800 -> HTC TyTN.