Вам нужно будет избежать обратного слэша (экранированного) в первом аргументе, поскольку это регулярное выражение. Замена (второй аргумент - см. Matcher # replaceAll (String) ) также имеет особое значение обратных косых черт, поэтому вам придется заменить их на:
theString.replaceAll("\\\\", "\\\\\\\\");