How do I disable command-control-up/down from doing anything with spaces?
You should be able to disable them through Prefs > Keyboard > Shortcuts > Mission Control, and then uncheck "Move left a space" and "Move right a space".

Those aren't actually the default shortcuts to switch spaces though, and there shouldn't be any "message" when using the shortcuts, so it sounds like it might be another app doing the hijacking, not OS X itself. Are you using any window managers or similar that might be implementing this? BetterTouchTool, Keyboard Maestro, SizeUp or whatever. Have a look through your login items and see if it still occurs with no background apps running.