When you checked System preferences -> Keyboard & Mouse, did you also check Dashboard & Exposé on the chance that the space key was inadvertently assigned in there?
If you're certain that the known-good keyboard really is good, check if there's some oddball third-party software conflict by
Starting Up in Safe Mode. Also use System Preferences -> Accounts to create a new administrative user account, log into that freshly-created troubleshooting account, and see if the spacebar works correctly. If it does, check the user preferences back in the normal account: open Applications -> Utilities -> Terminal, then copy and paste the following and press return:
find ~/Library -name '*.plist' -exec /usr/bin/plutil -lint {} \;
You can also download
Preferential Treatment (which provides a GUI front end to the plutil command).