Ayuda

[guille_el3]

Ante nada, una recomendación:
Si puedes partir el flujo de tu programa en 6 partes, probablemente puedes llevar esas seis partes a funciones distintas, de manera que tu código sea mas facil de leer, y cuando falle puedas ir a buscarlo de manera más sencilla.
Por ejemplo, podrias hacer algo como:

Código:

#include <stdio.h>
#include <stdlib.h>
#define MAX 30

struct datos               
{
       char nombre[MAX];
       int fijo;
       int movil;
};

void borra_buffer_teclado();

int main(int argc, char *argv[])
{
  int opcion, i;
  int datos_agenda;   //el numero de contactos que tenemos en nuestra agenda
  struct datos *contactos;
  FILE *fichero;
  
imprimirMenu();

opcion = obtenerOpcion();

  switch(opcion)
  {
      case 1:
                      
           fichero = fopen("datos.txt", "r");
if(fichero == NULL)
               printf("\nERROR\n");
           else{
datos_agenda = getDatosAgenda(fichero);
contactos = getContactos(fichero,datos_agenda);
introducirNuevoContacto(contactos);
}
           fclose(fichero);                                          
           
....
  }  
  
  system("PAUSE");	
  return 0;
}

Ahora, independientemente de lo anterior, ¿sabes en que lugar falla? ¿solo deja de funcionar o te da un error?
Para averiguar donde falla no se si hay una forma más feliz de debuggear en C (salvo con herramientas de debug que me parecen igual de infelices =P) que usar printf's en aquellos lugares donde piensas que puede fallar.

Particularmente imprimiria algo por pantalla dentro del do/while que lee los caracteres, y luego dentro de las partes importantes del switch.

Suerte!