If the color is the problem you could possibly try to print the PDF to PDF via the free and open source
PDFCreator "printer" driver and set the Color to Black and White or something.
But from my experience the reason why PDFs look crappy is because the kindle scales the page to fit the screen which in turn causes the text to loose "boldness".