Here's the list of supported processors: http://www.gigabyte.com/support-downloads/cpu-support-popup.aspx?pid=3270
Any of the Phenom II X4 or X6 processors are going to be a great upgrade, but new availability is drying up on those. A Phenom X4 965 Black edition for $85 or a x6 1045T for $110 (both at Tigerdirect) would both be excellent choices and should be about 3-4 faster for encoding video than your current setup.
Now in terms of maxing out the CPU, encoding is supposed to max out the CPU. That makes it finish faster. SO I would suspect your new processor also hits 100% during video encoding, you just finish 4x faster. The good news is that with 4-6 cores, you can still use the machine while it is encoding as long as you don't do anything else CPU intensive. Some video encoders do let you specify number of cores to use, but many just use what's there.