Did you make sure the new fuel pump had movement too it. I had a new one that was stuck away from the push rod. I had to pull it off, and move it a couple of times to free it up. Also, if that rod sticks pushed away from the cam, it would not allow the pump to operate. I don't know if those rods go bad or not. You might pull it out and wipe it off, then throw a little lube on it in case it's just a little sticky. In my case, I had added some Lucas at a prior oil change and wonder if it could halve caused the rod to stick. Not sure though. Along with the priming suggestion above, this should solve it. I just kept spraying starter fluid until it was primed enough to run. Hope this helps.
-Adam