A occhio e croce, guardando il codice, direi di provare modificando alcune cose:

1. dichiarare nulli i padding e i margin degli elementi[*].
2. impostare gli elementi <a> come block-level con display: block anziché float: left (sono flottanti già gli elementi[*] che contengono i link).
3. non impostare l'altezza degli elementi <a> con height perché hanno comunque line-height che "ne fa le veci".

Altro per ora non saprei...magari vedendo la pagina...