Io uso xine, ma mi sembra di ricordare che, una volta installati i codec e le libdvd anche Kaffeine aveva funzionato subito; di sicuro non l'ho mai ricompilato. Ora non posso controllare, in ufficio ho win...

Installa e prova.

PS: non ricordo di altri codec oltre a quelli del link.