well other than taking you through what may have caused this
to answer your question directly I have a tutorial on reducing/ ridding yourself of digital noise. and you merely need convert from 72 to 300 ppi by using the images sizing feature available in most software and be sure to NOT resample when adjusting this resolution.
if you have the ability to use the LAB mode in your program then this tutorial will work for you LAB and a blur like gaussian blur i hope this helps you
http://www.scrapbook-bytes.com/galle...hp?photo=22089
I also have a tut on sharpening in LAB mode as well.
i hope this helps
Tanya