Ancore-o ( ^ é o início da linha) para que o A seja correspondido apenas se for o primeiro caractere:
$ letter=A; id=MYNEWIDSTRING; sed "/^$letter /s/[^ ]*/$id/2" file
A MYNEWIDSTRING EXTERNAL
B CC32480A3247F84A SYSTEM
C EC2A63F12A63B76C EXTERNAL
a propósito, se você quiser passar variáveis para sed , mas precisar de citação strong, lembre-se de ativar e desativar a citação ao adicionar aspas duplas às variáveis - feio, mas provavelmente a melhor prática em geral:
sed '/^'"$letter"' /s/[^ ]*/'"$id"'/2'