This was going to be a second comment, but turned out too long, so I incorporated my original comment and expanded further.
It's probably a matter for your print driver rather than your output (and therefore technically off-topic). But what happens if zoom right in on the PDF on screen? I'm assuming you get solid grey. Try changing the "quality", "dpi" or "mode:economy/normal/..." settings on your print driver, and also any options regarding downloading fonts.
While it is true that changing the printer driver settings is a local fix, if they are the problem, you have no choice. Fundamentally a (typical) laser printer can only print pure black and white, any grey must be printed by some form of halftoning and control of that is likely to be beyond the scope of a document format.
You could also see what happens if you generate a bitmap with a similar shade of grey and print that - ideally in a PDF. As the printer driver may well handle bitmap and raster data differently this may appear to offer a way out, but it will cause more problems than it solves.
In cases such as your example, you may find that a darker grey or a colour (often 100% red or blue) would provide an adequate workaround, or even, as you've used italics already, just use black.
Incidentally, how is the graph produced and displayed in your latex file - I'm guessing it's an image, but what format?