Nope, I haven't seen that problem. I'm using RH8.0 with their latest kernel, the Nvidia 4191 drivers. I run Xine, and it displays DVD's FULL screen, crystal .. I'm running pretty much the same packages as you, but using Xine. That's goes the same for AVI's, MPEG's and well as VCD's, all show up great at full screen.
I forgot to mention, and at the same 1280x1024 resolution..
I would check your XF86Config file to see that there isn't something that shouldn't be there, or that there maybe something missing...