I'm aware of this problem, but didn't find out where it comes from (it's strange because it depends on some computer).
This should work when you use the two best qualities though.
when I render a video and say better quality the quality is very very grained. Haven't tried it at best quality now as this would take over 8 hours for me heh
That's partly why there are those quality levels. If you're not able to wait 8h, you still have the option to have a less good video. 
----------------------------------------
Emmanuel Puybaret, Sweet Home 3D creator
