Did your previous keyboard use a PS2 connector (round plug)?
If so, the system will most likely require the drivers for the wireless keyboard be installed before it will recognize it. Even though the drivers are most likely native Windows drivers (meaning they are included with XP), the system needs to be booted to Windows for them to load.
You will most likely have to connect a PS2 keyboard (round plug) in order to correct the issue.
For what it's worth, here is a video tutorial on how to connect a wireless keyboard (& mouse): http://tinyurl.com/57sgvr
[b]side note:[/b] If a USB keyboard doesn't work prior to booting up, it may be that Legacy USB support is disabled in the system's BIOS.
Here's how to ultimately correct that:
When the computer boots, hit the Delete key (DEL) and F1 repeatedly. This should allow you to enter into the BIOS settings area of the system. Not knowing what type of system you are using, I suggest DEL & F1 because they are the two most common ways to enter the BIOS.
Once in the BIOS settings, enable Legacy USB Support. Consult the computer's or motherboard's manufacturer for more detailed instructions.