Ok, I have redone the whole strafe animation. He no longer goes sideways but in fact, runs to the left (and right) much like current animations. It looks a lot better and was a lot faster to do as well (as I've reused the other run animations I've made).
A new version has been uploaded: http://ai.kurotorobert.com/nexuiz/model ... nim_b2.pk3
EDIT: For those who don't want to download and test, here's a video:
http://www.youtube.com/watch?v=-oRoXsl7ZqU