You’re not doing anything wrong – it just doesn’t work that way (anymore). Styling of :visited was used as a security hole, so browser manufacturers basically eliminated alternate styling for :visited except for a handful of properties (e.g. ‘color’, ‘background-color’)
See: http://hacks.mozilla.org/2010/03/privacy-related-changes-coming-to-css-vistited/