for an FPGA, you'll have a lot of fun the first time you try a design at Fmax/2 or higher. (as a general rule). for example, on a Virtex-5, which as a max rated speed in the 500MHz range, a design at 125MHz is fairly easy -- only the most complex logic fails to meet timing. At 250MHz, you start thinking about what the code will likely infer -- is it too complex? At 400MHz, you start getting into the region where not only must you look at things like the logic complexity, but also you must fight with PAR. once you get below 3ns periods, you really begin to realize how difficult 1ns+ routing delays can be. This becomes a HUGE issue as some elements are relatively sparse, like DSPs and RAMs, and routing to/from these locations can start eating up even more time. At 400MHz, you will be trying to trick the tools into working correctly. For xilinx, you'll likely be using smartXplorer a lot, as MAP/PAR cost tables become magical ways to get the tools to find a good solution. You'll start seeing congestion issues for large designs as well.
My advise is to look at your design. In almost every case, you should be able to run substantial portions of your design at less than 400MHz. This will help out tremendously. You shouldn't start out trying to build an entire design at 400MHz. Perhaps you can compute twice as much in the same cycle by doubling the hardware area. Until you run out of area, this will work very well -- 200MHz is reasonable to deal with.
Try building any of your previous code for a 400MHz clock. Most likely anything you wrote that is still readable won't work @ 400MHz.