Você acabou de cometer um erro de digitação, o pacote real desejado é chamado libx11-dev (com minúsculas x ). Então o comando seria:
sudo apt-get install libx11-dev
sudo apt-get install libx11-6
Se você pesquisar libX11-dev em Ubuntu Packages , ele retornará libx11-dev e não libX11-dev (observe o X ). Certifique-se de digitar o pacote corretamente antes de tentar qualquer comando de instalação.