Hi there. Rotating then doing cleanup is your best bet, unless you wan't to do what the person before me said, go higher resolution then drop it down again, but that could have negative effects as well (such as detail loss, Photoshop will probably cut out minor colors).
Rotate, then cleanup.