El problema esta en usar scanf, si usas fgets (con stdin) y sscanf te funcionara, igual es mejor usar fgets que gets asi podes especificar el tamaño del buffer en cuestion. Usando estas funciones no tendras que recurrir a fflush para flujos de entrada (su funcionamiento en ese caso esta indeterminado).
Ejemplo:
Código:
char input[80];
fgets(input, sizeof(input), stdin);
sscanf(input, "%d", &num_nombres);