Hi,
This may or may not help...
I have found that using powers of 2 in the output resolution, e.g. 1024 * 512, can sometimes help, and make sure that the camera is horizontal. (x rotation = 0). My guess is you may have already tried this...but sometimes..it works!
Rgds
Chris