Claro...
Observa, desgranando los parámetros
quien es reamplazado = frase[0].Substring(0, 1)
quien le sustituye = frase[0].Substring(0, 1).ToUpper()
frase[0].Replace(quien es remplazado, quien le sustituye)
Como quiera que el carácter a remplazar (0,1) es la 'e', y que se remplaza todas sus apariciones por 'E'... pués el resultado obtenido es correcto, pero no el deseado...
Prueba con:
frase[0] = "elefante valiente"
Verás que todas las 'e' acaban siendo mayúsculas. Con solo 2 'e' en una palabra tan corta, es posible que te cueste más verlo claro...
Si lo que buscas es poner (solo) la primera letra en mayúsculas, hay varios modos, he aquí uno de ellos:
string s = frase[0].substring(0,1).toUpper // toma el primer caracter y lo comvierte a mayúsculas
frase[0] = s + frase[0].substring(1,frase[0].length-1) // concatena detrás el resto de la cadena.
.