It sounds like there is EXIF data in the jpeg which records which way 'up' is. Either this info is getting ignored when you upload but is not ignored on your PC - explaining why the image looks the right way up when you view it on your desktop, but the wrong way up in Magento, or vice versa.
Can you use an art program or bulk convertor like XnView to either apply or remove the EXIF data before uploading? Then you might need to manually rotate some images.