Seemed? Why did it SEEM that way? I gotta' ask again, Did you test the fuel pressure? A hole in the gas line (including leaking injectors) would make for low pressure, and the pump and regulator could be working fine.
If not, you either HAVE TO start there, or pay a mechanic tons of cash to do the same Fully Automatic Assault Wallet repair technique. Spray new parts at the problem, and hope to find a faulty one.
Either buy a fuel pressure guage, and do a static and dynamic pressure test, or pay a mechanic to do THAT ONLY, and post back results.
Static is 'motor off' fuel line pressure, to see 1) what it goes to, and 2) how long it takes to bleed down. I think this is what vetteos was gettin' at. If the injectors let the fuel pressure out, leaking into the cylinders, you'll have black smoke at a cold start in the am. Just like a garden hose with a leaky sprayer. With a new pump, the pressure is probably good, but you need bleed down time. Hope you still have your old pump - it's probably still good, and you can put it back, and buy the fuel pressure gauge when you return the pump..
You probably do not need a dynamic pressure test (motor running pressure), since starting up is the problem. It still is a good thing to know.
See youtube for fuel pressure test vids.
