I haven't been down this particular road, but it sounds like X11::Xlib is a light wrapper around libx11-dev and x-dev. Did you install those libraries yet?