What program are you using to rotate them? The Windows Picture and Fax Viewer will increase the size considerably. Eg, I've just rotated a 151KB picture and result is now 271KB.
Just a thought here! When you rotate an image it has not the same file attributes as the original image file. Try saving the newer rotated image as a new file and then try to post it.