I haven't used SoX extensively since Mandriva was called Mandrake. It looks like the newest version of SoX has a very good converter. The comparison graphs I just found and linked below show that the different converters seem to optimize for different parameters; Shibatch SSRC appears to focus on passband width, while libsamplerate's Secret Rabit Code has better time domain response. If you're using SoX VHQ, you probably can't do much better, unless you find that its time domain response causes undesirable artifacts.
As for the 16kHz sample, listening to the .m4a files directly did give much better results than playing them through Flash.
Anyway, good luck with ZenCoder.
http://sox.sourceforge.net/SoX/Resampling
http://src.infinitewave.ca/