Swap file, even with 512 or more of RAM is usually expected. Although I don't know if that's your problem...
Check the video_out option in your settings. I believe kaffiene is a frontend to xine-lib and not mplayer so it will likely be xine looking options. Depending on your videocard, you may even be able to use Xvmc or Xxmc (if it's xine). Otherwise, try xv as it's the best for most users. All others use some sort of software, either for scaling or for processing or for both; and all of them use software to process the codec. Xv uses hardware scaling and output, but it can sometimes be hard to get it working.
Jittery video on that much hardware is either the above mentioned, or hard drive I/O. If this is from a CD/DVD-ROM drive, you may want to check hdparm and ensure that dma is turned on. It may be network latency if this is being played back over an NFS mount.