I think TheSeven is right about the nasty plastic packaging of the FPGA, it is the major bottleneck for its heat to dissipate. Isn't this chip available with a metal top?
Glad to hear you got it working better! Is the heatsink then attached to the PCB in some way? I don't think the thermal grease will hold onto it very well (for long at least). Or maybe I misunderstood what you used...
Nope, no metal packages available for the Spartan 6 FPGAs, unfortunately. Looking at the published thermal specs for these FPGAs (UG385, page 341), though, I don't think the case is that bad. Obviously metal would be better, but we're just trying to move less than 10 W here. In rough numbers, keeping the thermal resistance from case to ambient under about 5 degC/W should be good enough. This is possible with the stock heatsinks and a good fan next to the board. The key then is that we have two parallel thermal paths: through the case and through the PCB. Adding those in parallel means that the total thermal resistance from junction to ambient is reduced a lot. This is why airflow over the board itself is very helpful! If you want to eliminate whole board airflow, you need to drastically reduce the thermal resistance of the heatsink.