Expressão Regular

veja se assim te ajuda:

/**
	 * Substitui todos vl1 por vl2 do texto.
	 * @param frase 
	 * @param vl1
	 * @param vl2
	 * @return
	 */
	public static String replaceAll(String texto, String vl1, String vl2) {
		
		boolean continua = true;
		String textoSubstituido = texto;
		while (continua) {
			int posInicial = texto.indexOf(vl1);
			if (posInicial != -1) {
			    textoSubstituido = texto.substring(0,posInicial);
			    textoSubstituido += vl2;
			    textoSubstituido += texto.substring(posInicial+vl1.length());
			    texto = textoSubstituido;
			} else {
				continua = false;
			}
		}
		return textoSubstituido;
	}

Se eu usar o seu exemplo não vai funcionar, pois teria que substituir uma TAG por vez, ou seja:

1. [ B] ->
2. [ /B] ->

E assim poderia acontecer algo do tipo:

Ficaria assim:

E deveria ficar assim:

Isso não pode acontecer…

Guilherme,
acho que é isso que vc esta querendo

String regex= "\\[B\\](.*)\\[/B\\]";
		String x = "Uma [B]frase qualquer, [B]cheia [U]de[/U] palavras[/B] para podermos[/B] tratar.";  
		
		while(x.matches(".*"+regex+".*")){
			x = x.replaceAll(regex, "<b>$1</b>");  
		}
		System.out.println("x:"+x);

a outra expressão regular que vc usou tem o grupo ([^\[]), com ela vc não que os itens que estão dentro da lista por isso troquei por (.) assim vc vai subistituir qualquer coisa

bueno:

Guilherme,
acho que é isso que vc esta querendo

String regex= "\\[B\\](.*)\\[/B\\]";
		String x = "Uma [B]frase qualquer, [B]cheia [U]de[/U] palavras[/B] para podermos[/B] tratar.";  
		
		while(x.matches(".*"+regex+".*")){
			x = x.replaceAll(regex, "<b>$1</b>");  
		}
		System.out.println("x:"+x);

a outra expressão regular que vc usou tem o grupo ([^\[]), com ela vc não que os itens que estão dentro da lista por isso troquei por (.) assim vc vai subistituir qualquer coisa

Boa, é quase isso, fiz uma pequena alteração.

Se fizer do seu jeito, não vai funcionar com essa frase:

Tem que mudar a expressão regular para:

String regex= "\\[B\\](.*?)\\[/B\\]";