Ubuntu's based on Gnome, so I think you mean gnome-terminal. Usually installed X system includes at least one of simple terminal emulators, xterm or eterm. Try to launch one of them, then type gnome-terminal in it, and check error message.
If you haven't got any other terminal emulator, switch to console with Ctrl-Alt-F2, login, and try to launch gnome terminal with DISPLAY=:0.0 gnome-terminal. You can switch back to X environment by pressing Alt-F7