Eu tive o mesmo problema no Ubuntu Linux 11.10, até atualizar o Parallels (Parallels Desktop- > Check For Updates) e reinstalar o Parallel Tools na Ubuntu Virtual Machine. Agora a resolução muda automaticamente conforme eu redimensiono a janela Parallels. Coerência e modo de tela cheia também funcionam.
Em uma nota secundária, o modo Coherence não funcionará no Ubuntu com o Unity habilitado.
Para executar o disable Unity no Ubuntu 11.10, execute este comando em um terminal:
$ sudo apt-get install gnome-session-fallback
Em seguida, efetue logout e login após selecionar "Gnome Classic" no ícone de roda dentada.