So after a few months of being carefully packed up (and turned off), I finally had enough free time to unpack my office again and get things going.
To my surprise the keyboard wasn’t working correctly. Even though it was showing full charge the K800 would randomly loose connection to my PC. This made for a very frustrating work experience.
After some poking around the intertubes I discovered that the likely cause was the crappy batteries used by Logitech. So a quick run to the store and I had my self a new set of NiMH AA batteries and installed them (by the way, when you open the battery case, it appears that one of the batteries is stuck under a black plastic tab, this is no problem to move out of the way and successfully remove the old batteries).
So the new batteries are in, the keyboard is allowed to charge overnight to ensure full charge and again, to my surprise, no connection to the PC.
As you may or may not know, I run Linux (Kubuntu) as my desktop operating system (FreeBSD for the servers) and was able to track down a nice set of tools for these Unifying dongles.
After a quick compile and execute I was able to place the mouse dongle into pairing mode and successfully paired both keyboard and mouse back to the PC. Now no more problems and life is good again.
I really love this keyboard and was very happy to find out that the fix was both cheap and simple, and would recommend it to anyone in the future.