This is a fairly common issue. At a minimum the FPGA and uC need to know the other is ready to go. You add another requirement of the FPGA starting up the uC. Can you post a schematic showing the reset handshake signals between the FPGA and uC? Include details like any pullup resistors. Also, perhaps a timing diagram of what you think is happening or any scope trace of actual timing.
Thinking ahead, why not use the internal startup of the uC to reduce the problem to just the two parts knowing if the other is ready. This can be done with two signals with pull-up resistors which go low when the part is ready. Then, if the FPGA has a problem, the uC can startup independently and respond to the problem. Usually the FPGA will have an optional "Configuration Done" output for this purpose with no logic required. A port pin on the uC can be controlled in software to go the other way.