Video playback may always be slow if there is no hardware decoder, and even slower if there are no SSE (or other proprietary equivalent) commands on the CPU. Since you have problems with the screen savers as well, it is most likely that you're not using the correct driver for your video card.
Anyway, for the SSE issues:
Check your current kernel version: uname -a
If the tag at the end is only "-i386" (generic 80386, no multimedia instructions) then you should look for and install a kernel which does have SSE:
* check your CPU type: more /proc/cpuinfo
* find a suitable Linux image: apt-cache search linux-image
If you have a Pentium-6 (or compatible) family of machine, you can replace 'libc' as well:
apt-cache search libc6 | grep 686
For the graphics card issues we need to know what hardware you have:
'lspci' lists your PCI Bus IDs and "Vendor String"
'lspci -n' lists your PCI Bus IDs and VendorID:ProductID code
Post the lines that refer to your graphics hardware.