Hola,
En el HTML la clase .menu la posees dentro del tag <nav> y en el CSS le estas haciendo referencia como si este fuese una clase del tag <ul> "ul.menu a:hover".
Como lo veo la solución es super sencilla si aun quieres seguir teniendo el ul para acceder al hover del los link puedes hacerlo de la siguiente manera:
Código HTML:
.menu > ul a:hover{
color:#fffff;
background:red;
}
Eso es todo, saludos.