No creo que tengas problema si te pones un poco, por lo menos a mi las de mates me fue las mas faciles sacarlas y las de programacion mas dificiles.

Prueba a cambiar esto :
-Con esto comprobamos letra por letra en la frase2.

int inicio=0;
int fin=letra2-1;
 
	while((inicio<fin) && (frase2[letra1]==frase2[letra2])){
	    inicio++;
	    fin--;
 
	}

si el while sale porque fin e inicio son iguales es que es palindromo y tirara por el if, si no se cumple la igualdad de las letras tirara por el else y no será palindromo

if (frase2[inicio] == frase2[fin])
	{
		printf("\nTu frase es palindroma!");
	}else ......

Le estuve echando un vistazo por encima y puede que me equivoque pero bueno alomejor el fallo que tienes ahí es en la variable fin.
Creo que tienes que igualar el fin a true ya sea en el if o en else sino te repetira el while hasta que le des a salir.
Si te fijas tienes el fin = true cuando tecleas salir y ahí el while no te va a seguir por lo tanto tendras que igualar la variable a true en otro bucle para que te salga y no te entre de nuevo.