Three more thoughts.
My experience is that it is the developer and not the paper. However, if you have taken the paper out of the fridge and it has condensation on it, then perhaps there will be weird effects. However, the presence of black specs suggests tar in the developer.
If you cannot stand to dump your new developer, perhaps careful filtering will remove the heaviest contamination. The trickiest thing is to get as little air into the dev as pos. Clean out as much gunk as pos while the developer is out of the tank.
To test the paper, get a small amount of fresh dev (with starter) in a tray. Warm the tray to approx your working temp and develop an unexposed piece of paper. My guess is that it will turn out white.