Aqui o cheese também não queria abrir, fui na central de programas do ubuntu baixei o "synaptic", removi o cheese pela central, abri o synaptic e procurei por cheese e instalei alguns pacotes, reiniciei o sistema e o cheese abriu normalmente, o que você pode fazer também é usar algum mensageiro instantâneo para configurar tenta usar o empathy chama alguém para uma chamada de video e veja se consegue efetuar a chamada.