If flushing std doesn’t work, then try reading in the extra characters and discarding, as suggested here.
This will work:
#include <string.h>
#include <stdio.h>
int main(){
char nombre[10];
char mensaje[80];
int c;
printf("Type your name:\n");
scanf("%9s", nombre);
while((c= getchar()) != '\n' && c != EOF)
/* discard */ ;
printf("Now, type a message:\n");
gets(mensaje);
printf("%s:%s",nombre,mensaje);
return 0;
}