Nasty brown crap? That doesn't sound good, but it's a major clue!

How does the fuel filter look? If the old ones is still in there, change it out and cut it open to see if it's crapped up.

If that rusty crap got into your injectors, then I would say try some other ones.
Was the tank and fuel system flushed out when the pump was taken out? If not, the new pump will probably be the same way