Hi guys, an update for you all!
So I got sick of waiting for a solution from either Yubico or Microsoft, so I decided to look into the issue in earnest myself. I found a number of other devices with similar issues moving from Windows 8 to 8.1 - external USB 3.0 HDDs and some mobile phones were the most common. I came across a dodgy workaround here, which has now restored my Yubikey NEO functionality on my laptop:
http://forum.xda-developers.com/showthread.php?t=2598155Essentially this replaces the base USB port drivers (usbport.sys and usbhub.sys) with Windows 8.0 versions instead of the 8.1 versions. It's pretty dodgy, but it does work. The workaround no longer applies for the mobile phones thanks to MS KB2917929 but it does work for the Yubikey NEO.
Obviously modifying the default Windows drivers could have some unforeseen issues, but I haven't had any so far. YMMV.
TL,DR: replace usbport.sys and usbhub.sys with Windows 8.0 versions to restore NEO functionality in 8.1.