Well, upgrading will always help, but you can changing the "vo" device used. If you are using mplayer, then you can try:
mplayer -vo xv foo.avi
Do "mplayer -vo help" for more details.
Which graphics card are you using? If you are using an nVidia or ATI card, then try installing the official drivers. (Ubuntu has apt-gettable nvidia drivers)
I've also noticed that win32 codecs are a bit slow, and may give problems.