java replace German umlauts

I have the following problem. I am trying to replace german umlauts like ä, ö, ü in java. But it simply does not work. Here is my code:

private static String[][] UMLAUT_REPLACEMENTS = { { "Ä", "Ae" }, { "Ü", "Ue" }, { "Ö", "Oe" }, { "ä", "ae" }, { "ü", "ue" }, { "ö", "oe" }, { "ß", "ss" } };
public static String replaceUmlaute(String orig) {
    String result = orig;

    for (int i = 0; i < UMLAUT_REPLACEMENTS.length; i++) {
        result = result.replaceAll(UMLAUT_REPLACEMENTS[i][0], UMLAUT_REPLACEMENTS[i][1]);
    }

    return result;
}

An ä remains an ä and so on. I do not know if this issue has something to do with encoding, but the String contains the exact character I am trying to replace.

Thank you in advance

This finally worked for me:

private static String[][] UMLAUT_REPLACEMENTS = { { new String("Ä"), "Ae" }, { new String("Ü"), "Ue" }, { new String("Ö"), "Oe" }, { new String("ä"), "ae" }, { new String("ü"), "ue" }, { new String("ö"), "oe" }, { new String("ß"), "ss" } };
public static String replaceUmlaute(String orig) {
    String result = orig;

    for (int i = 0; i < UMLAUT_REPLACEMENTS.length; i++) {
        result = result.replace(UMLAUT_REPLACEMENTS[i][0], UMLAUT_REPLACEMENTS[i][1]);
    }

    return result;
}

So thanks to all your answers and help. It finally was a mixture of nafas(with the new String) and Joop Eggen(the correct replace-Statement). You got my upvote thanks a lot!