I'm not entirely sure what you're referring to when you say I must, "center [my] image first," but I will note that the selection box does not appear misaligned prior to rotation. Apart from that, I am selecting it before rotating, and yes, I am using the latest version of paint.net.
Sorry for the late reply; I expected to get email notifications if I check the 'follow topic' checkbox, but this seems not to be the case.