non ho capito se hai risolto tutto, giacchè intanto avevo scritto...

tag.classe:pseudoclasse, quindi
a.google:hover

non hai visited, e non avendo una regola per l' a generico quando il link è già visitato non rientra in nessuno delle altre regole

al posto della regola per a:link
codice:
a:link, a:visited
{
 color:#000;
 text-decoration : none;
 font-weight : bold;
}
puoi risparmiare anche qualcosina: questo dovrebbe essere identico ma + compatto
codice:
a {
 text-decoration:none;
 font-weight:bold;
 color:#000;
}
a:hover {
 background-color:#c00;
 color:#fff;
}
a:active {
 background-color:#f00;
 color:#fff;
}
a.google:hover, a.google:active {
 background-color:#fff;
 color:#000;
}
ciao :)