I see, it was the word boundaries. You can try either of these, the former will color the colon and the latter will not.

Code:
on $&^*:text:/\b(New|Done)\x3A/S:*:{
  var %a = $regsubex($1-,/\b(New:)/g,3\t)
  var %a = $regsubex(%a,/\b(Done:)/g,4\t)
  echo -mirctbfl normal $iif(#,#,$nick) $+(<,$nick,>) %a
  haltdef
}


Code:
on $&^*:text:/\b(New|Done)\x3A/S:*:{
  var %a = $regsubex($1-,/\b(New)(?=:)/g,3\t)
  var %a = $regsubex(%a,/\b(Done)(?=:)/g,4\t)
  echo -mirctbfl normal $iif(#,#,$nick) $+(<,$nick,>) %a
  haltdef
}