Non riesco a riprodurre il tuo problema, con questo codice:

codice:
public class Tiime
{
	public static void main (String [] a) {
		String test = "Viale della Libertà , 9";
		test = test.replace ("Ã ", "a");
		System.out.println (test);
	}
}
A me stampa correttamente:

codice:
C:\Users\Francesco\Desktop>java Tiime
Viale della Liberta, 9
Onestamente non saprei da cosa possa dipendere ...