I had very similar problems when I started out... I use Nero 6 and I was having playback problems (such as it jumping all over the place, read errors,etc)... the best solution I found wasn't with my software but with my DVD player.
If you can, the best ********** you can make is to get a DVD player with DivX and MPeg4 features. I got a recordable one for £100 which was pretty good considering it plays absolutely everything I chuck at it. I was advised this by someone on here a while ago, and its really paid off.
If you check the playback of your burned DVD's on your computer and they play fine but not in your stand alone DVD player, then maybe you should consider this option... its well worth it.