Sharptail:I rotated the photos in my Mac photo program first. That failing, I rotated them in Photoshop Elements. That failed too.
If you're using iPhoto, make sure you're uploading from the file it re-saves as, and not the original file, that should include your changes.