Fala ae pessoal, consegui resolver. 
  
Existiam dois problemas: 
  
1)Na definição da estrura em vez de definir uma caractere eu mudei para um ponteiro para um caractere 
  
2)Limpei o buffer do teclado usando o comando setbuf(stdin,NULL) 
  
Agora ta funcionando certinho, segue o código para o pessoal que talvez esteja com o mesmo problema corrigido 
#include <stdio.h>
#include <stdlib.h>
#define TAM 3
struct node // aqui eu só criei a estrutura mas não aloquei espaço em memória
{
    char *info;
    struct node *next;
};
typedef struct node *NODEPTR; // Esse é um ponteiro para a estrutura node (nó)
NODEPTR getnode() // Cria um novo nó na lista
{
    NODEPTR p;
    p=(NODEPTR)malloc(sizeof(struct node));
    return p;
}
void freenode (NODEPTR p) // Libera a memória associada a um nó da lista
{
    free(p);
}
void insafter (NODEPTR p, char x) // Insere um elemento x após o nó p (que é o primeiro nó da lista)
{                                // Essa função insere os elementos depois do nó p, assim ela empurra
    NODEPTR q;                   // os elementos que já estão na lista para frente
    if (p==NULL)                 // por isso quando imprimimos os elementos aparecem em ordem trocada com
    {                            // com exceção do 1 primeiro elemento, pois inserimos depois dele
        printf("Problema de alocacao");
        exit(1);
    }
    q=getnode();
    q->info=x;
    q->next=p->next;
    p->next=q;
}
void delafter (NODEPTR p) // Deleta o nó seguinte ao nó p
{
    NODEPTR q;
    if ((p==NULL)||(p->next==NULL))
    {
        printf("Remocao nula");
        exit(1);
    }
    q=p->next;
    p->next=q->next;
    freenode(q);
}
void imprime_lista(NODEPTR p) //imprime todos os elementos da lista
{
    NODEPTR q=p;
    while(q!=NULL)
    {
        printf("\n%c\n",q->info);
        q=q->next;
    }
}
NODEPTR insere_lista(int x) // cria uma lista com x elementos e retorna um ponteiro para o inicio da lista
{
    NODEPTR p;
    int i;
    char ch;
    for(i=1;i<=x;i++)
    {
        printf("\nEntre com %d elemento da lista:",i);
        scanf("%c",&ch);
        setbuf(stdin,NULL);
        if(i==1) // No primeiro nó temos que fazer q->next apontar para NULL
        {
            p=getnode();
            p->info=ch;
            p->next=NULL;
        }
        else
            insafter(p,ch);
    }
    return p;
}
int encontrou(NODEPTR p, char V[], int t)
{
    int i;
    NODEPTR q=p;
    for(i=0;i<t;i++)
    {
        if(q==NULL)
            return 0;
        else
        {
            if((V[i])==(q->info))
                q=q->next;
            else
                return 0;
        }
    }
    return 1;
}
NODEPTR encontra_string(NODEPTR p, char v[])
{
    NODEPTR q=p;
    while(q!=NULL)
    {
        if(encontrou(q,v,TAM))
            return q;
        else
            q=q->next;
    }
    return NULL;
}
int main()
{
    NODEPTR p,r;
    char v[TAM],teste;
    int x;
    printf("Digite o numero de elementos da lista:");
    scanf("%d",&x);
    setbuf(stdin,NULL);
    p=insere_lista(x);
    imprime_lista(p);
    setbuf(stdin,NULL);
    printf("\nDigite uma string com %d elementos:",TAM);
    gets(v);
    r=encontra_string(p,v);
    if(r==NULL)
        teste='z';
    else
        teste=r->info;
    printf("\nA funcao encontra string retorna %c\n",teste);
    return 0;
}