The whole issue of libdvdcss being “illegal” in DMCA–enlisted countries seems to be mute now, from my perspective… so long as your intent is only to watch movies that you have legally obtained (and not fincancial gain), then it should be fine — if it's good enough for the MPAA, then it's good enough for me. This would seem to me to work well with Australia's existing copyright law, which specifically grants fair-use copying and playing anyway, and goes against the dogma of the DMCA.
Now playing with Gentoo as my latest Linux of choice (I got fed up with RPM dependancy problems, and Gentoo being source-based solves my other issue with binary-based distributions, where I felt like a 2nd-class citizen when using or accessing source code).
So, I’ve got Xine working, but can only use shared memory for the video decoding. This is great if I want to capture screen shots, but not for high-speed movies such as The Matrix, or even just reading the credits on The Lord of the Ring. So need to “fix” the performance.
Also while reading around, I discovered Mplayer. This looks like it’s worth a download…