You have a camera which has a sensor so that when you rotate for verticals, an orientation tag is embedded in the image's EXIF data. This feature is most useful for direct printing to printers, not for editing.
Photoshop (in my case, CS) reads the EXIF data, understands this tag, and auto-rotates the image in the editor. Which is dandy for PS CS itself. But when saved as a smaller file, say for web use, it isn't rotated. Yet PS CS always shows that it IS rotated. And if rotated again in PS CS, it's now normal for web, but 90 degrees out in PS CS! Confusing, isn't it?
The solution? Depends on the camera. If your camera allows for it, make sure the "orientation" feature on your camera is turned OFF. Now my camera, an Olympus E300, always records the orientation, and my orientation ON-OFF function simply controls the viewing of the image on the rear LCD (!). And since Photoshop CS has no ability to ignore the orientation tag, rotating's can be a real pain. I'm currently using Exifer as a batch ability to simply strip away the EXIF data before I begin the editing process (from copies of the originals, just to be safe).
Hope this helps...