O problema é que ~/.bashrc não é lido por shells de login e, portanto, ele não é lido pelo shell obtido ao efetuar login via SSH.
Como você já notou, ~/.profile é lido por shells de login, então é uma maneira de definir a cor, mas isso não afeta o MOTD.
No Debian, o MOTD é armazenado em /etc/motd ; aqui está um comando que irá anexar as seqüências de escape corretas no início e no final do arquivo:
printf '\e[0;32m' | sudo perl -i -pe 'if($. == 1) { $_ = <STDIN>.$_ }' /etc/motd; printf '\e[0m' | sudo tee -a /etc/motd
O\e[0;32mdefiniráacorparaverdenoinício,o\e[0mredefinirátodososatributosnofinal;Destaforma,oMOTDéalteradosemafetaroqueéimpressodepois;Sevocênãoquiserredefinirosatributosnofinal(afetandooqueéimpressoapósoMOTD),apenassolteoúltimocomando:
printf '\e[0;32m' | sudo perl -i -pe 'if($. == 1) { $_ = <STDIN>.$_ }' /etc/motd

