For the last couple of years, this bug has been plaguing poppler – the PDF rendering engine that drives Evince in Ubuntu. The problem was that images weren’t being anti-aliased properly, and hence looked very bad when viewing them in PDFs such as the Ubuntu Manual.
It was fixed upstream and released in an unstable version recently that originally wasn’t going to be included in Lucid, but thanks to some persuasion by the Ubuntu Manual Team and a backported patch by Josh Holland, it was packaged for Ubuntu and hit Lucid updates today!
Here’s a before and after comparison. Click it to view at 100%.