I've had this problem again and again, and I finally had to reverse engineer a video that I had seen transcoded properly. Its bit rate was around 2572k. So I took my audio and video streams and muxed them with the command below. The pixellation finally disappeared.
ffmpeg -i movie.m2v -b 2572k -i movie.mp3 final.avi
Hope this helps you or someone, because I know what an annoyance that problem is.