Have you ticked Anti-Aliasing? At least in older versions it is hidden away in the Image Size window.
Thought I had tried that, but apparently you have hit Apply and then click Done and do it again in order for the de-selected option to take affect. THANKS!
You are welcome, s.