Do you have access to a scope? Check your gate to source voltage.
Does the drain voltage drop after the 1st solenoid energizes?
Ignitions generate incredible electrical interference. A high frequency lightning storm. The spark plug firing voltage can vary with engine load.
The interference could affect your mosfets and or PIC.
The electrical interference is both conducted and radiated into your circuits.
Proper Layout, shielding, twisted pair wiring, etc... may be needed.
Tires can also generate electrostatic electrical interference.
Try diagnostic LEDs to make sure your program is executing the code.

Good Luck