Você pode precisar de outros pacotes dev x11 também. libxext-dev, libxpm-dev, libxrandr-dev, libxrender, mas talvez não, se suas compilações estiverem corretas.
Agora, a queixa de não encontrar -lX11 é ímpar, já que deve estar no libx11-dev, mas talvez o .so seja apenas um link para a biblioteca real no pacote libx11-6. Nesse caso, todos os outros pacotes dev também precisarão do pacote da biblioteca correspondente: libxext6, libxpm4, libxrandr2, libxrender1
Use o apt-file search libxrandr.so etc. para encontrar os pacotes necessários.