That is correct, ATI doesn't support XvMC, and restricted drivers are the same as teh proprietary drivers.
I like to use htop for process/CPU monitoring:
then you can run htop from a terminal while you are running mythfrontend to watch something in hidef. Or you can ssh into your box from another machine and run htop. Are all the channels you can tune hidef? do you have problems with non-hidef digital channels?
sudo apt-get install htop
Also, what are you TV playback settings? sometimes playing with those can reduce CPU usage...