Get a profile for your newspaper press that uses pure black and no UCR.
I'm sorry, can you expand a bit on what you mean by that?
You can apply a newspaper's ICC Color Profile to you psd image. "UCR" means under-color-removal ... in other words, where there is solid (or mostly) black, there are little or no other colors in with the black. It saves ink on newsprint, and helps the printed sheet dry quickly. Contact your newspaper, and ask for the ICC profile.
One more thing ... you will need to apply the profile BEFORE converting from RGB to CMYK.
Couple questions -
This particular paper does not seem to have a specific ICC profile - I tried using US Newsprint (SNAP 2007), but that actually turned some pure blacks into mixed blacks. Is there a standard color ICC profile I can use that converts mixed black to pure?
Also, if I have already converted to CMYK am I out of luck...?
If you convert back to RGB prior to changing any profiles, you should be ok.
If the newspaper geniuses don't know what profile they need, then it's up to you.
In Photoshop, select Edit > Color Settings > CMYK > Custom CMYK.
Under Custom CMYK > Ink Colors, select "SWOP (Newsprint)", and click the radio box "UCR".
Also you might set Total Ink Limit to something less than 300, like 280.
Now when you convert your RGB to CMYK, there should be a lot less CMY under your K.
I hope that helps.
Remember to sing "YMCK" to the Village People tune ... :+)