Bingo!

Changed the class with
hciconfig hci0 class 0x100114

Which gives us:
Nokia-N810-23-14:~# hciconfig -a
hci0: Type: UART
BD Address: XXXXXXX ACL MTU: 384:8 SCO MTU: 64:8
UP RUNNING PSCAN ISCAN
RX bytes:14026 acl:26 sco:0 events:324 errors:0
TX bytes:4238 acl:26 sco:0 commands:135 errors:0
Features: 0xbf 0xee 0x0f 0x46 0x98 0x19 0x00 0x00
Packet type: DM1 DM3 DM5 DH1 DH3 DH5 HV1 HV3
Link policy: RSWITCH HOLD SNIFF PARK
Link mode: SLAVE ACCEPT
Name: 'N810'
Class: 0x100114
Service Classes: Object Transfer
Device Class: Computer, Palm
HCI Ver: 2.0 (0x3) HCI Rev: 0x6cc LMP Ver: 2.0 (0x3) LMP Subver: 0x6cc
Manufacturer: Cambridge Silicon Radio (10)

And it pairs!

After all that the iPhone was right. The N810 was pretending to be a keyboard. Now to get tethering working ...

Cheers,
John