Long cold start cranks, certainly sound like a bad HPFP to me. And just because you had it replaced doesn't mean it's a good part. Afterall I believe the HPFP's are rebuilt units. And there were several versions of the HPFP. Even in the last year there is a new version.
You should also have the fuel line pressure switch replace next to the HPFP. Its on the fuel line that feeds the pump. The switch is like $100 part.
As for new SW... I hope BMW doesn't load the same SW they have for 135i's that keeps the wastegates open(until 3.5K rpms) and kills throttle response. This sw also has a very smooth idle and quiets the injector(dieseling) noise while the engine is running - which is why I believe BMW NA uses it to prevent customer complaints.
Looking at the injectors is also a good idea.
Another thought is that the EWS immobilizer is kicking in. There is a chip in the key fob and the car has to see the right code. IF it doesn't the DME will not let the engine start.
I had this problem on my 135i twice. It threw a code though, but later that code erased itself. I realized my problem was I was putting the key fob into the slot(I don't have CA on my car) too quickly and THEN trying to start the car. I just wait half a second before hitting the start button.
Dackel