Lately, I experienced the very same problem: text and graphics produced with pdflatex do not appear totally black. I noticed this on the (laser-printed) test print that I got from the printing company that will print my thesis. (although, when I printed the same document on my own laser printer, the result was perfectly black).
What happens is that the 'black' in the document (as far as I could see, it is stored in the pdf as "0% gray") is converted to a different color scheme, in which it is mapped to something which is not perfectly black. As a result, the printer will use a dithering pattern (black dots with white spots between them) to 'fake' the not-perfectly-blackness. This can be easily seen in two ways:
- The edges of all texts are ragged. This is not a result of the fonts being bitmapped (they're not), but a result of the fact that, also on the edges, there are white spots which make the edge look ragged.
- Using
\rule{2cm}{2cm}
should give a perfectly black rectangle. Because of the large area, you can easily identify a regular pattern, being the dithering pattern of the printer.
Years ago, I experienced the same problem with other PDF's I made (not with Latex) when going to the local copy shop. The problem could be solved by using a different color space in Adobe Acrobat (if I remember correctly, we used Adobe RGB to solve it). Apparently, in that color space, full black (or 0% gray) was mapped onto the most black color available.
As for the printing company, I explained the problem to them and they were able to fix it. I don't know how they did it though, but they were able to do it.