El problema está en que al poner dos "tags" de color juntos ( o tres, o lo que sea ), tu expresión va a tomar como el [ color ] inicial siempre el primero de todos y el [ /color ] final siempre el último de todos. Sin importar la cantidad que haya ni como estén anidados. Por eso, podrías cambiar tu RegEx asi :
Código PHP:
<?php
$msg = reg_replace(
"/\\[color:([A-z0-9]*)\\]([^\\[]*[A-z0-9]*)\\[\\/color\\]/",
'<font color="\\\\1">\\\\2</font>',
$msg);
?>
De esa manera, valida los tramos de código que NO contentan un "[" dentro.