One of my first guesses apart from what you have already done is to check that your receiver is within close proximity of the keyboard, perhaps there is a range related issue, or something is blocking the signal. Try a different usb port or placing your keyboard nearer the receiver.
Perhaps try repairing the keyboard, or to a different pairing number. Or try connecting to a different computer/device.
After all this perhaps a warranty claim with all the testing and information you can provide.