As a beginner getting involved with FPGAs it's important not think that you're writing source code, but that you're describing hardware. Taking that bit of advice goes a long way to describe you're timing constraint problem.

As an analogy, when you create a schematic in you're favorite capture program, you have to choose the components and wire them appropriately. Then you have to lay out the PCB and route the wires. FPGAs give very basic logic building blocks and they add in some unique hardware like the DCM, SRAM Blocks, and hardware multipliers for Xilinx. With VHDL or Verilog you are describing the schematic and building components from basic building blocks.

Keeping the above in mind, FPGAs work best when logic/hardware is ran in parallel. This is especially hard to grasp if you're familiar with C and now entering the world of descriptive language.

Putting all of this together, the Xilinx tools takes your description of the hardware and has to physically route the logic inside the fabric of the FPGA. This is analogous to an auto-router in your favorite layout program. If you've played with auto-routers in the past, you may have found that the auto-router may just quit sometimes or never complete.

Xilinx tools does have an option to increase the amount of time the tool tries to accomplish the timing goals by routing means, but I forgot how to do that and you may have better luck on the Xilinx forums to figure that one out. I have seen someone respond in the past about that.

The way to solve the problem step-wise is to find out in the summary under timing ( it's a subsection ) where all the time is going. This way, you can tell if it's the routing method, or the logic. Xilinx is pretty good about keeping the time down during the routing process. Keep in mind that wires do take time to pass through even though they may be very insignificant.

Chances are that your logic is taking a long time and the routing method is slightly changing during each .bit file generation causing this timing constraint problem.