Pronto, eu reescrevi todo o código usando alguns outros conceitos baseados em outros documentos que eu andei lendo, vo posta ai pra vcs darem umas dicas, como trocar uns comandos, usar outro metodo para fazer alguma coisa, esse tipo de coisas,...

#include <stdio.h>
#include <unistd.h>

/* Protóripos */
void menu(void);
void inserir(void);
void corrigevars(void);
void reginserido(void);
void listar(void);

/* Estrutura e ponteiros */
typedef struct regs{
char nome[50];
char tel[10];
struct regs *anterior, *proximo;
} lista;

lista *primeiro, *proximo, *anterior, *atual, *gravar;

/* MAIN */
int main(){
menu();
}

/* Funções */

void menu(void){
char opcao;
do{
system("clear");
printf("\nAgenda Telefônica v0.1 by c0dek\n--------------------\n");
printf("\nEscolha a sua opção no menu abaixo:");
printf(" \n(I) - Inserir novo registro");
printf(" \n(L) - Listar todos os registros");
printf(" \n(S) - Sair");
printf(" \n-----\nSua opção: [ ]\b\b");
opcao = getchar();
if(opcao == 'I' || opcao == 'i')
inserir();
if(opcao == 'L' || opcao == 'l')
listar();
if(opcao == 'S' || opcao == 's')
exit(0);
} while (1);
}


void inserir(void){
system("clear");
printf("\nAgenda Telefônica v0.1 by c0dek\nInserindo novo registro\n--------------------\n");
gravar = (struct regs *)malloc(sizeof(lista));
if (gravar == 0 ){
printf("\nMemória insuficiente para alocação...");
return;
}
printf("\nInsira o nome: ");
gets(gravar->nome);
gets(gravar->nome);
printf("\nInsira o tel: ");
gets(gravar->tel);
corrigevars();
return;
}

void corrigevars(void){
if (primeiro == NULL ){
primeiro = (struct regs *) malloc (sizeof(lista));
primeiro->proximo = gravar;
primeiro->anterior = gravar;
gravar->proximo = primeiro;
gravar->anterior = primeiro;
reginserido();
} else {
printf("\nJah contem entradas...");
anterior = primeiro->anterior;
proximo = primeiro;
anterior->proximo = gravar;
gravar->anterior = anterior;
gravar->proximo = proximo;
proximo->anterior = gravar;
reginserido();
}
return;
}

void reginserido(){
char lixo;
system("clear");
printf("\nAgenda Telefônica v0.1 by c0dek\nNovo registro inserido...\n--------------------\n");
printf("\nSeu novo registro foi inserido com sucesso, veja abaixo:\n");
printf("\nNome: %s", gravar->nome);
printf("\nTelefone: %s", gravar->tel);
printf("\n------------------\nPressione qualquer tecla para continuar...\n");
lixo = getchar();
menu();
}

void listar(void){
char opcao;
if( primeiro == NULL ){
printf("\nNenhum registro encontrado...");
menu();
} else {
atual = primeiro->proximo;
do{
system("clear");
printf("\nAgenda Telefônica v0.1 by c0dek\nListando todos os registros\n--------------------\n");
printf("\nNome: %s", atual->nome);
printf("\nTelefone: %s\n", atual->tel);
printf("\n-------------------\nComandos: (P) para avançar | (A) para retroceder | (B) para voltar para o menu\nSua opção: [ ]\b\b");
opcao = getchar();
switch(opcao){
case 'p':{
if(atual->proximo == primeiro)
atual = primeiro->proximo;
else
atual = atual->proximo;
break;
}
case 'a':{
if(atual->anterior == primeiro)
atual = primeiro->proximo;
else
atual = atual->anterior;
break;
}
case 'm':{
menu();
break;
}
}
} while (1);
}
menu();
}