Parece que a localização binária da sua tela não está no $ PATH sendo usado por sh. Então, quando você sudo, porque você não está invocando o shell de login para configurar um novo ambiente, o comando não existirá. Você pode verificar isso verificando algumas coisas.
torne-se root:
$ sudo -s
# which screen
/some/path/to/screen
# echo $PATH
A maneira mais fácil de corrigir isso é especificar o caminho completo para a tela no comando que você está usando:
$ sudo -n -u root sh -c "/some/path/to/screen -d -m -S testscreen sh -c \"echo asd; echo qwe\""
Se isso não resolver o problema, seria útil capturar se o sh tiver algum outro problema ao iniciar a tela:
$ sudo -n -u root sh -c "set -x ; screen -d -m -S testscreen sh -c \"echo asd; echo qwe\""