Keyboard works on one computer but not the other

I have an aluminum wireless keyboard that came with my Mac Pro (Early 2008). Some time ago, it just stopped working. I tested the bluetooth mouse and a few other bluetooth peripherals to check that it wasn't the Mac Pro's bluetooth that was malfunctioning. I was convinced that the keyboard was broken, and was about to take it to the Apple Store to get it fixed when I thought that maybe I should test the keyboard on another computer. When I did that, it worked perfectly, but it still does not work with my Mac Pro. I've tried changing the batteries and removing the pairing from my Mac Pro. When I try to re-pair it, the Mac Pro is unable to discover it. Thank you in advance for your help.