Cannot find X include files anywhere...

You probably need to install the libx11-dev package (*-dev = development), which provides the required include files like Xlib.h, etc.