Ultimo tentativo ... intanto, il codice che hai scritto dovrebbe essere

codice:
for (v=0;v<utentimemorizzati;v++)
{
  for(i=0; rubrica[v].nome[i]!=0; i++)
    rubrica[v].nome[i] = tolower(rubrica[v].nome[i]);
  for(i=0; rubrica[v].cognome[i]!=0; i++)
    rubrica[v].cognome[i] = tolower(rubrica[v].cognome[i]);

  for(i=0; rubrica[v].citta[i]!=0; i++)
    rubrica[v].citta[i] = tolower(rubrica[v].citta[i]);                
}
ma NON E' QUELLO che ti dicevo di fare perché così modifichi i DATI inseriti e non va bene.

DEVI LAVORARE sulla strcmp e DOCUMENTARTI (non l'hai neanche tentato di fare !) per fare confronti indipendenti dal case.