Does this only happen in PackageKit, or also in other applications?

I don't know, but I would strongly suspect a theme issue.  (That was a Fedora 18 live USB that I've dd-ed over already; it'll be a few days before I return to it again. It's not a problem in GNOME 3.4 / Fedora 17.)

Let me add some experience (from playing with Adwaita) that might help. Look at Epiphany 3.6's dropdown "awesome bar."  In Adwaita 3.6, the URLs below the page titles are displayed grey always, while the page titles above the URLs are displayed black always, or white if selected. These are the same colors that are used in PackageKit's updater interface. I suspect that in the high-contrast theme, you'll see the page titles in black if unselected change to white when selected, but the black URLs remain black (and therefore become invisible). But this is a lot of speculation for something that is easy to check - my apologies for not doing so.

In Adwaita, the always-grey color, I call it the "subtitle color," is "insensitive_fg_color" (or something it is assigned to). But the high contrast theme is different enough that I don't really know what's going on and I didn't see an obviously equivalent color in it.

Thanks for the report Michael.

The use that gnome-packagekit does of theming colors there is slightly wrong (it fetches the insensitive color from the theme as you were guessing); you can also see in Adwaita that the second line of selected text stays black whereas it should be different.
A better fix needs to be done in the application, but I now pushed a fix to the HighContrast theme so that the insensitive color is always defined, which is the best we can do from the theme.