When Emacs runs in a terminal, its input is a series of characters. When Emacs runs using its graphical UI, its input is a combination of keypresses, giving it a vastly wider range of possible inputs. For instance, the keypress C-` (control backtick) can be bound to a function when Emacs is running with its GUI, but not from a terminal (even a terminal emulator, which is itself a graphical application), because there is no such character as Control-Backtick (not in ASCII, not in ISO-Latin-1, not in the Universal Character Set).
You are trying to send the non-existent character C-M-SPC from a terminal. The fact that
xterm makes it work is nice, but you shouldn't expect every terminal to fake out Emacs' input so that you can press key combinations that do not map to real characters in a terminal.