As versões recentes do Vino (o servidor VNC que você provavelmente está usando no Ubuntu) exigem criptografia por padrão, que, infelizmente, praticamente nada mais fornece!
Esta página é um lugar que irá informá-lo e como corrigi-lo. Basicamente, você está apenas desligando a opção "require-encryption" no Vino.