Well according to their web site: http://www.microsoft.com/hardware/en-us/p/universal-mobile-keyboard#details it says:
Requires a PC that meets the requirements for and has installed one of these operating systems:
- Microsoft Windows^®^8+ and Windows RT
- iOS 6+
- Mac OS 10.7+
- Android 4+
- Works with tablets and smartphones that have Bluetooth HID (Human Interface Device) keyboard support.
I would have expected 8.1 to count as 8+
I confess I missed the light grey 6pt text that says "Does not work on Windows Phone" ..! ahh the joys of the "Modern" UI
As a last ditch attempt, last night I cleaned out all the Bluetooth accessories from the Surface's list, and rebooted. I pressed the tiny button on the right of the keyboard for more than 3 seconds, and lo and behold, it appeared in the list and I was able to pair.
I've just been using it here at work, I was reading an MSDN article , went to type, and it had gone to sleep. Nothing I did would wake it up.
Flaky beyond belief.
My thanks to all the contributors, but I've got an Amazon return voucher. I'll try the Logitech.
I hope someone from MS reads this...its a shame, I like the design.