Você está tentando combinar, para o grupo 2, qualquer coisa, exceto : até : , mas há dois pontos no tempo, então você não corresponde. Você pode tentar substituir o [^:] por . e, provavelmente, obter os mesmos resultados, a menos que tenha um : em algum outro lugar da linha, ele corresponderá até a última ocorrência dessa sequência.
Talvez um padrão melhor, no entanto, seja
sed -r 's/(\[DEBUG])( \[[[:digit:].: ]*] [^:]*: )(.*)/${RED}${DEFAULT}${RED}${DEFAULT}/'