My last teaching job included advising the student newspaper and it's conversion to digital photography (which may seem anachronistic now, but then it was cutting edge) - we were ahead of most newspapers and magazines.
SB likely has the answer in the question what's changed?
I would expect the occasional over/under inking in a random copy of a given issue, but a systemic problem that is consistent is something should be attributed to either the source (you) or something consistent in the chain (art director, plant personnel, printing).
If you have an unsympathetic editor (or simply a language barrier), I would first suggest that you make sure your end is in order by ensuring the monitor is correct and that your output is exactly what you want it to be and expect it to be when printed - keep in mind that newsprint has tonal limits.
When you're 100% of that, take a finished print for one of your stories that can be printed (be realistic in the tones a newspaper can print) and you'll have an image that you'll want to shepherd through the process. Find out what's wrong with that image. It'll be a pain in the ass for you and them, but I _think_ the art director will get it and the press people will, too. Nobody wakes up in the morning wanting to fail.
Essentially, "I want it to look like this" is your argument. You don't give a rat's ass what it takes, you want them to do their job; after all, you've done yours.
My best, and if we can be of any help, please put an area up for posting,