I think Brian had it right, it doesn't look like you're interpolating properly. I was able to reproduce the jaggy look of your resized image by resizing with "nearest neighbor" after "resample image:". Make sure you're using Bicubic. If it's defaulting to nearest neighbor, you might want to see if you can change that in your preferences.
Also, I wasn't clear on whether you're using Photoshop or something else. If you don't solve your problem, please clearly define every step you take and with what software.