Hi first, i suggest you use xubuntu 12.04 instead of 10.04... you will encounter less issues.
in addition to the amd proprietary driver, you need to also get
sudo apt-get install xvba-va-driver libva-glx1 vainfo
Run 'vainfo' to see what your gpu supports decoding.
I do not know if mplayer or vlc come precompiled with xvba/vaapi support for amd cards, but you can always compile them your self if they don't. maybe someone else knows.