Is the keyboard usb or ps2?
I had problems when I changed my wireless mouse with a new one, I had to ditch the ps2 to usb convertor and it worked fine.
Sometimes the best way is to unplug the wireless keyboard stuff and your new keyboard with the machine turned off. Turn the machine on let it boot and when it gets to windows put the keyboard in then if necessary hit the restart button not ideal, but has worked on a few gypy keyboards at work.