It could be the anti-aliasing or lack of, on your selection tool or perhaps you are feathering the edges on your selection tool. Try turning those off in the check boxes and see if you still have the same problem. Perhaps it could also be the interpolation of your selection transform tools? Try changing it to none and see if the problem still occurs.

So I just did both of these things, as you suggested, and the selection was unable to rotate. I would rotate it, and it would bring up a loading bar at the bottom that said "rotating" and then it would just stay put...