Это происходит потому, что (является специальным символом в соответствии с синтаксисом регулярного выражения (который используется replaceAll).
В этом случае вы должны воспользоваться советом Skeet и использовать «заменить», но, чтобы дать вам представление о том, как работает версия регулярного выражения, вот пример:
public class test {
public static void main(String args[]) {
System.out.println("\\");
String s = "(foo)";
System.out.println(s);
s = s.replaceAll("\\(", "\\\\(");
System.out.println(s);
}
}