I wouldn't remove it. Given it is the default terminal emulator for the Unity/Gnome desktop environment, there could be some obscure program/script that use it unconditionally and you'll have an error (probably two years from now when you didn't remember what can have caused it).
The preferred way is:
Install the new terminal emulator, for example
sudo apt-get install terminator
update-alternative method to choose it:
[romano:~/tmp] % sudo update-alternatives --config x-terminal-emulator
There are 8 choices for the alternative x-terminal-emulator (providing /usr/bin/x-terminal-emulator).
Selection Path Priority Status
* 0 /usr/bin/terminator 50 auto mode
1 /usr/bin/gnome-terminal.wrapper 40 manual mode
2 /usr/bin/koi8rxterm 20 manual mode
3 /usr/bin/lxterm 30 manual mode
4 /usr/bin/rxvt-xpm 8 manual mode
5 /usr/bin/rxvt-xterm 10 manual mode
6 /usr/bin/terminator 50 manual mode
7 /usr/bin/uxterm 20 manual mode
8 /usr/bin/xterm 20 manual mode
Press enter to keep the current choice[*], or type selection number:
...and that should be it. If you have probelms, you can look here: How can I set default terminal used in Unity?
Notice however that there is a bug/misfeature of the underlying library that makes that all the things that use the "open in terminal" will not respect the selection above. The bug was reported and acknowledged in 2010, there is a patch available, but it's still here. I wouldn't hold my breath for a fix.
A system-wide workaround could be to remove the
gnome-terminal binary and replace it with a link to
x-terminal-emulator --- should work most of the time...
Alternatively, you you have in your
$HOME/bin directory before
/usr/bin (as everyone has, I suppose) you can simply
ln -s /usr/bin/terminator $HOME/bin/ (no privileges required) and glib will happily use the link instead of the real