[Frango100]

Welcome to the garage.
The first thing which came up in my mind when reading the header was: fuel filter/regulator or o-ring in fuel pump assy. But you changed both already. Was the complete fuel pump assy replaced, or only the pump cartridge?
Did you check if fuel is coming out of the fuel rail after priming but not yet starting, just to be sure that there is not a pile of air in the line?
When you run it for a while, stop the engine and start after 10 minutes again, does it start normally or also long cranking time? Did you check the plugs after some cranking without starting to see if they are wet?
The crank sensor and cam sensor are used for fuel injection sequence and synchronizing. A bad sensor can/will prevent the engine from starting, but why would it then start after some cranking and not give problems anymore thereafter? I don�t want to say that it is not possible, but sounds strange.

 

[Frango100]

This could very well be your problem. Couldn´t find any resistance values, but the sensor is a NTC type (negative temperature coefficient) The higher the temperature, the lower the resistance and the lower the temperature, the higher the resistance. You probably could check this out doing the following: disconnect the connector on the temperature sensor (on the thermostat housing) and see if it start normally now. It will most probably set the MIL light, which has to be reset afterwards. But by disconnecting it, or it will use a preset value, or it measures a high resistance (thus low temperature). If it then starts normally or at least better (depending on which temperature it uses when it is a preset value), then you have found the problem.

 

[Frango100]

Good to hear that you have found the problem. The coolant sensor input is used for the fuel injector opening times and also for the idle air control stepper motor position. The PCM should regulate a rich mixture (via the injector opening time)and a higher idle rpm ( via the IAC position) when coolant is cold, which in your case it didn´t.
Did the engine start normally with the coolant sensor connector disconnected?
No parts of the old sensor stayed behind in the cooling system?