I've had this kind of thing before. Strangely enough, after I'd
changed my distro the same disc that didn't play then played. Try
different (or more up to date) versions of libdecss and libdvdread or
whatever they are. And obviously try cleaning the disc, but you've no
doubt already done that.
