Mine was/is doing the same thing...I made a post about it and here it is...
98-pathfinder-starting-weird-t591314.html
I don't know if this solved the problem but lately it's been firing right up! I took some electronics parts cleaner and sprayed/cleaned the connectors that sit on the passenger side valve cover. I was mainly trying to clean the connection leading to the knock sensor, so i sprayed the outside and inside of them. Can't really say that's what is was but that's all I've done to it...lol
Read the comments on my post because there was a mention of a check valve in the fuel pump.
Do you have a knock sensor code stored?
Another thing i have been doing but not all the time is turn the key to start...wait a sec or two then turn the key and starts fine.
Edit: I too have a new battery, alternator, fuel filter, spark plugs, and a clean IACV