Problema com acentos e caracteres especiais

Estou desenvolvendo um chat, em java, mas estou com um problema, com acentos e caracteres especiais.

Recebo coisas do tipo:

%20Parabéns%20ao%20Campeão

que na realidade deveria ser:

Parabéns ao Campeão

Com isto, consigo decodificar a url:

String msg;
try {
    msg = URLDecoder.decode(msg,"UTF-8");
} catch (UnsupportedEncodingException ex) {
    ex.printStackTrace();
}

Mas os acentos e caracteres especiais, nao consigo ajeitar.

Como posso fazer isto?

Grato