Not a bug, but a feature.
Pretty much every site I am aware of, and almost every commercial site I've worked on over the last 14 years uses the :visited selectors for specifying colours, background-images, underlines, etc. as part of the site design and to improve usability. As a developer, I wouldn't consider using something that does not conform to the standards. Web developers have used this for years because it's part of the CSS spec and thus considered safe.
And now Mozilla are seriously considering breaking widely used functionality and moving away from the standard, because they want to pander to a few paranoid beardies in sandals who wouldn't know usability and design if it bit them in the arse. Why, thank you very much.
I consider myself to be reasonably security conscious, but I find it hard to see what exactly the security issue is.
From what I understand, the only way this "bug" (and I use the term in the loosest possible sense) can be exploited is when the "attacking site" has a link to *exactly* the URL in its HTML / JS that the visitor has been to before. This means that the "attacking" site can't ask the browser to give up the history, but it has to ask whether it has been to URL xyz.
I would suggest that anybody worried about this has more pressing issues than keeping their browser history private.
BTW, @grumpy: "Site developers have done stuff according to the CSS specification, and now Mozilla is thinking about ignoring web standards so that everybody has to fix their style sheets in order to placate a handful of paranoids." There, fixed that for you.