Make sure you turn off "preserve Illustrator editing" on the PDF options, as that embeds the entire AI file inside the PDF. Given the destination I'd them use the PDF/X-1a:2001 preset which will flatten transparency and ensure everything's in CMYK.
The default raster resolution of 300dpi is normally perfect for commercial printing, but newsprint tends to run lower-quality; if you can't get a 300dpi file small enough then ask the paper what resolution they actually require (150, 100, etc.) and change the PDF export settings to match.
If you have Acrobat you can optimize the PDF. When I use this method, PDFs are mostly shrunk to 10% of the original file size or less.
In addition to what Dave has suggested and I agree, take a look at your original image resolution. For newsprint, you can use 150ppi. Make sure you are not scaling the image files in Illustrator, bring them in at 100%. If you can ustomize the PDF settings, then create another version of "High Quality Print"; set the image resolution to 150ppi and the output resolution to 1270dpi. Try to reduce the amount of layers, going as far as creating a flattened copy of the original file. Another thing you can try is creating the PDF in Photoshop. I sometimes do this for proofing via the internet. Here's how I do it: with a flattened copy open in Illustrator > Export as a .tif @ 150ppi CMYK > In Photoshop, open the .tif and... > Save As > Photoshop PDF with a JPG compression of 8. Open the PDF in Acrobat or Reader and check the size, print a proof.