Granted, some of you are concerned about people finding out the sites you visit, but what about a real world problem (or two)?
Some time back, there was an attack that threw a phony dialog pop-up saying that your timeout had been expired at your bank site. Combine that with being able to see *what* bank's site (and whether or not you have been at it recently). This could even be injected through a compromised ad-server system or the like. Maybe you don't even have to visit my site. There's some moving parts in there, but things like this, combined with click-happy-and-fill-in-personal-data user syndrome could make for some pretty sophisticated attacks.
From a private organization's perspective (many of whom have private systems, blocked off from the outer world) ... this can also be used to help map their internal network from the outside (just by one of their users visiting a site). Think about that after you visit your interal cisco web interface and then merrily tab into some other site.
I am particular about who I allow to set cookies, but not so much about my history (except that I do wipe it .. and other 'private data' when FF closes). don't know that I'll change that behavior yet, but will probably modify the config on visited site styles as some have suggested here.