I have been very frustrated by OS X's (Preview app) handling of image rotation. You can, of course, have Preview rewrite the EXIF tag and make the image appear rotated, but as soon as you go to put that image on the web or use it in Word, etc, that rotation simply doesn't exist. What's more, even after you apply new icons to a file (i.e. using CocoThumbX), the icons might not show up correctly.
Until now, I used a combination of Preview (to modify the EXIF orientation value) and PhotoToolCM (to do lossless JPG rotations) to achieve images that look correct both in Preview and in non-EXIF/web apps. Well, I finally found a program that both rotates the image and the thumbnail consistently! Enter the freeware Cheese by Stuffware.co.uk. This is a bare-bones program that has two basic purposes: rotate pictures properly, and allow you to add comments easily (it can also create web pages from your images).
Once you've rotated your pictures, here's a fast way to get your thumbnail icons to show correctly (i.e. refresh):
Mac OS X Hints
http://hints.macworld.com/article.php?story=20080424112720636