An update: Since I wrote this guide, vdpau has proven itself to be a mature, reliable and practical way of playing high definition videos on linux machines.

By far the easiest way to get pain free video playback in linux is just to buy a nvidia card. You can pick up a 9400 or something for only about £30, it's totally worth it.