You will likely need to convert each PDF to gif or png format. Then change the colors using -fuzz xx% -fill red_or_green -opaque black -transparent white. Then you will need to composite the two images over each other. You will need to play with the fuzz percent to catch all of the black/gray of the lines as there will be some graying of the black most likely. Fuzz does a fuzzy selection to get similar colors as determined by the percentage. If your images are truly b/w with no gray, then you can skip the -fuzz xx% part and just change black to whatever (red or green) and at least in one image make white become transparent, so that you can overlay the transparent image over the other one. It depends upon whether you still want a white or transparent background in your composite whether you make white in both images transparent.
Then if you really want you can convert the final result to PDF again.
Alternately, you can just use the compare function:
compare <compare option> image1 image2 differenceimage
Differences will show up as red by default, I believe. See http://www.imagemagick.org/script/compare.php
I am not sure if compare works directly with PDF files, but you can try. If not convert your images to png.