Only other thing I can think of is that Photoshop has the nasty habit of making images look like crap when not at round zoom numbers (12.5,25,50,75,100, for example all look fine. Anything in between looks like hell). Are you viewing the image at 100%?
Short of that I have no idea what else might be the issue, as you say it was a circle to begin with.