I've read all that twice now, but I followed it again anyway and it solved the problem.
It seems, rather stupidly, that when I have been installing the things it needed, such as 'libdvdcss' this was reinstalling them. 'libdvdnav' on the other hand, didn't reinstall at all. I think the problem...