Você cobriu todas as coisas normais em que eu conseguia pensar. Aqui está o que eu tentaria em seguida:
Teste para problemas de rede:
Executar
wget -O /dev/null --report-speed=bits https://github.com
em alguns computadores do laboratório e altere a URL do projeto que você está testando.
Se isso não resultar em algo, talvez tente:
ping -c3 github.com
E observe se a rota é diferente.
Teste de problemas do Git:
Execute o seguinte com seus comandos git normais:
GIT_CURL_VERBOSE=1 GIT_TRACE=1
Além disso, você pode recriar a imagem desta máquina?