/*
El principal problema que tenía tu código es que, a pesar de modificar i y j adecuadamente, cunado volvias a invocar a palindromo_recursivo, se ejecutaban las primeras líneas y se hacia i=0, j=strlen(...) con lo cual se perdía su valor.
i y j deben ser por tanto parámetros de entrada de la función, y quedaría así:

(también he cambiado alguna tontería mas que he comentado)
*/

#include <stdio.h>
#include <string.h>

int palindromo_recursivo (char array_tratada [], int i, int j)
{
    if(j<=1) // El  == no contempla el caso de cadenas vacias. Estaria mejor 'if (j<i)' (basta recorrer medio array)
    {
       // No se si se puede 'return valor=1' (creo que sí) pero en cualquier caso está muy desaconsejado
        return 1;
    }

    else
    {
        if(array_tratada[i]==array_tratada[j])
        {
            return palindromo_recursivo(array_tratada,i+1,j-1);
        }
        else
        {
            return 0;// Deberías usar 0 en vez de 2 para denotar falso (ya que 0 se evaula como falso, y 2 se evalua como cierto)
        }
    }
}


int main() {
    char cadena[] = "olo";
    printf("Resultado: %d",palindromo_recursivo(cadena,0,strlen(cadena)-1));
    getchar();
}