Did you actually win Enmity of my Enemy? The FATE has to be successfully completed AND you have to get Gold. FATE difficulty is based on the number of people at the previous pop so if there are only a few people there and the FATE times out, next time it spawns you should have no problem clearing it.