It is likely your options for the Rectangle selection tool are stuck in some mode other than "Replace the current selection" (and since tool options are store per user, they might be surviving program re-installs).
Just check in the tool options for the the rectangle selection tool (double click the rectangle selection icon if the tool options is not visible),a nd ensure the very first option there "Mode" is set to "Replace the current selection".
There is another way to further check what is going on (and you might need if the problem persists) - after performing "paste" check the Layers dialog (hit ctrl + L
if it is not visible), and certify yourself you have both a "background" layer and a "Floating selection" there.
Another cause of your problem might be that you are for some motive consistently anchoring the floating selection after performing the Paste. (for that to happen, one just have to click on the image outside the pasted area). To avoid that, before trying any action on the image, after pasting, select the command Layer->To New Layer
from the menus: that will promote the pasted contents to a full layer that can't be "melded back to the bacjground" by chance. (again, watch the Layer's dialog to better understand what is going on)