I have a few options for you to consider:
Option 1: IO Contention
The disparity in your video encoding performance likely has very little to do with CPU. Rather, look into IO contention. While you're encoding, run top, and watch the value of %wa in the header. This is the percentage of time the server is having to wait for IO requests. You want this number as low as possible. On my systems, I start making changes if I see this number get any higher than 5% or so, averaged out over a 5-minute span.
If you are indeed seeing high IO contention, there are a few things you can do. First, and perhaps easiest, would be to move to a Provisioned IOPs (PIOPs) EBS volume. With these, you can specify how many IOPs you need. You'll pay extra for it, but it's by far the easiest way to increase IO performance.
If you don't want to do that for some reason, you can associate a bunch of EBS volumes to your server and stripe them together into a larger RAID0 volume. Aggregate IO will be greatly increased in this situation, but it's also much more risky, as the failure of any single EBS volume will destroy the data on that volume.
I'd recommend giving a PIOPs volume a try.
Option 2: CPU Throttling
Another thing to consider: you're running an m1.small. On these smaller instances, AWS is pretty aggresive with CPU throttling, so you may consider moving to a larger instance, possibly a High-CPU model, like the c1.medium. If AWS is throttling your CPU, you'll see high values in the %st (steal) column in the output of top.
Option 3: Outsource it
This may be a stretch, but why not try out AWS's Elastic Transcoder service? That will take all of the burden of encoding off of your server completely.
I received confirmation from Amazon that a vCPU is in fact a single hyperthread on a single core.
On a side note, this was news to the software vendor we were working with (one of the biggest enterprise companies out there) and they were nice enough to adjust the terms of the licenses for software running in AWS environments.
Best Answer
One thought I have. In my experience with AWS instances using top may or may not return realistic values for CPU usage (usually not). Check cloudwatch and see if it is showing a high CPU usage. This especially applies to micro instances, on those top is absolutely useless.