Como Scott mencionou nos comentários da questão, o atalho de teclado Ctrl + Alt + T deve normalmente iniciar uma janela de terminal. Outra maneira que posso sugerir é abrir o menu de aplicativos e procurar por programas de terminal alternativos.
Ao usar o Lubuntu (um derivativo do Ubuntu usando o LXDE), tenho a tendência de encontrar de 2 a 4 vários programas de terminal disponíveis no menu de aplicativos. Não tenho certeza se há um caso semelhante na edição de desktop do Ubuntu (eu só executo uma instalação de edição de servidor), mas certamente vale a pena procurar.
Parece que alguns dos problemas encontrados podem ter sido causados por permissões. Isso também valeria a pena explorar.