VLC tends to play DVDs really badly (on my G3 anyway). You really need a firmware patch to get them going properly. Sorry to hear that there isn't one available for your drive yet.
It's very frustrating for me, as here in NZ they sell DVDs from multiple regions, as all DVD players can play all regions. However I bought my iBook from the US and it is therefore region protected and I had to apply the patch. Speaking of the patch, it says that if it gets interrupted it can destroy your drive. So I start the patch, and when it finished, it came up with a big red stop sign or something, which made me think it had failed and killed my drive. But no, it had worked successfully, but whoever wrote the patch had decided to use a big red "fail" icon just to scare people.