The "halo" of halftone dots is caused by Photoshop whenever you rasterize something into Grayscale mode. Photoshop is a photo editing tool, so it applies anti-aliasing to the edges of objects to ease the transitions between colors. While this works well for it's intended purpose in photos and in elements used in video or the web, it doesn't work well for printed line-art as you see in your example. Converting vector based files (many PDFs or EPSes) into raster based files (Tiff, PSD, JPG) will always cause this to some extent.
The anti-aliasing comes out as a halftone dot, and depending on your linescreen and resolution it can be very noticeable. Generally it's less noticeable when printing to higher linescreen values. On the lower resolution sample you provided, it looks much more gray because there are fewer pixels for Photoshop to use in the transition so more of the solid type has to turn gray to make it look smooth on screen.
The best solution for this is to not use Photoshop to edit vector based files. If you're given a PDF then the best solution is to edit it with a program that was designed for it, like Acrobat Professional and/or Pitstop. Use the built in preflighting functions to make sure they are viable and then either place in InDesign or save as an EPS out of Acrobat for placing in Quark.
As a workaround, if you have no other choice, you might be able to rasterize it in Photoshop at a higher resolution (around 1200 dpi) do your edits and then convert to Bitmap mode using the 50% threshold option. That will convert everything 50% gray or less to white and everything 51% gray or darker to black. Bitmap mode doesn't use any anti-aliasing so you won't get the halo.
Of course you won't get any grays either so it won't work as a single file for any ads that have grayscale elements in them. I've seen people go as far as to make two separate image "layers" for an ad in Photoshop and then combine them in InDesign or Quark. One "layer" is in bitmap mode at 1200 dpi and contains all the solid elements like text, the other layer is placed behind the text layer and is in grayscale mode at 300 dpi and contains all the pictures and elements with grays in them.
Hope this helps,
Shawn
