I had the same problem. Have you tried Neat Image?

Made a considerable difference for me. It's sharpening abilities are pretty good too.

At current exchange rates you can get the Pro version for under ?29.