Eu não sei a causa raiz ou uma correção verdadeira, mas eu tive o mesmo problema após atualizar para o 13.04 (não no Parallels, no entanto), e em um palpite eu rodei o xcompmgr, que o corrigiu. Se isso funciona para você, talvez isso seja uma pista para alguém mais capaz de lidar com isso.
Anteriormente, eu só precisava do xcompmgr se eu quisesse efeitos especiais ou transparência orientada pelo gerenciador de janelas, mas talvez as versões recentes do gnome-terminal mudassem para a transparência baseada em composição em vez de qualquer método usado antes?