A parte che, nel modo in cui hai dichiarato le variabili, GCC si rifiuta addirittura di compilarla, una roba così 
Ad ogni modo l'errore sta qui
codice:
scanf("%s\n", &cell);
Che c'entra il newline in uno scanf?
Codice funzionante:
codice:
#include <stdio.h>
#define MAX 100
main()
{
char nome[MAX],cognome[MAX],mail[MAX],tel[MAX],cell[MAX];
printf("Inserire il nome> ");
scanf("%s", &nome);
printf("Inserire il cognome> ");
scanf("%s", &cognome);
printf("Inserire la e-mail> ");
scanf("%s", &mail);
printf("Inserire il numero di telefono> ");
scanf("%s", &tel);
printf("Inserire il numero di cellulare> ");
scanf("%s", &cell);
printf("Come vuoi salvare il contatto?\n");
printf("1) Nella struct\n");
printf("2) Su file\n");
/* ...... */
return 0;
}