Ваша проблема newP = phrase.replace(c, ch);
Вы присваиваете последнее значение.
String newP = phrase;
for(int i = 0; i < phrase.length(); i++){
char c = phrase.charAt(i);
Boolean vowel = isVowel(c);
if(vowel){
newP = newP.replace(c, ch);
}
}
Лучшее решение, как ответил Алекс, просто добавьте строку,
phrase.replaceAll("[aeiou]", ""+ch);