Isso funcionou para mim:
service screen restart
Acredito que nosso servidor acabou de ter muitas sessões de tty em execução (que são as sessões de tela realmente) e não pode criar uma nova. Tivemos esse problema apenas uma vez antes e tivemos quase o mesmo tamanho de telas em execução.
Depois de encontrar o bug, também reinstalamos a "tela" digitando:
apt-get purge screen
apt-get autoclean
apt-get autoremove
apt-get install screen
apenas para garantir que seja um erro de configuração. Nós não tivemos nenhum problema desde então.
EDIT: Eu entrei em contato com o servidor hoster para aumentar o máximo permitido de sessões tty (o que você deve fazer também). O administrador então define o máximo permitido de sessões tty de 16 a 2048 (quase ilimitado).