Constraint data is being incorrectly held in memory by the constraints management system.
The current work-around is to close and re-open the project.
This problem has been fixed in the latest 10.1 Service Pack available at:
http://www.xilinx.com/support/download/index.htm
The first service pack containing the fix is 10.1 Service Pack 1.