It is not the rotation itself that is the problem, but saving the resultant file. If you're working directly with the pixel buffer you only do a lossless JPG rotation if the image height and width are multiples of 8 (or 16, in some situations). This is because once you've performed the rotation you'll need to save the resulting output as a JPG, and unless your dimensions factor into the block size you'll need to recompute. This SO answer covers it in more detail[1].
However, if you're not working with the pixel buffer this doesn't apply. You can use jpegtran (part of libjpeg), for example, which manipulates the JPG file directly and never decodes it. Many basic image viewers and editors (like the Windows Picture Viewer, and probably the iOS Photos app but I'm not sure) don't use this approach though.
[1]: http://photo.stackexchange.com/questions/12361/are-windows-p...
I've been looking around to see if ImageMagick could do rotation without degrading quality. (I'd also asked a question about that elsewhere in this thread.) So I assumed that most devices use something similar even for displaying on the screen. It appears I assumed wrong. :)
I saw your other comment about axis-aligned rotation not being too computationally expensive. In that case, why aren't iPhones doing it by default? Wouldn't their computation power be comparable to that of most of the cameras that rotate the images? Or are cameras better equipped to handle such transformations?
