So, how do the negatives look?

If you have a strong loupe or magnifier of some type take a good look. If the problem was caused by the negative the defects you see in the print should also be visible in the negative. If you can't see the defects in the negative then the printing is definately in question.