I found out why the sky wasn't working: it turns out that q2bsp (the new name for qbsp3) gets the flags that tell it if a face is part of the skybox by reading the headers of the texture files. It wasn't able to load the textures, so it couldn't work out that the sky-textured bits were actually sky.
One thing led to another, and I ended up rewriting not only the PAK loader, but just about all the code that messes around with filenames and directories.
A PAK file is basically a linear collapse of a directory tree into a binary object (it's entirely uncompressed) and I believe that the reason for doing it was to avoid the overhead of opening, reading and closing a lot of files. Anyway, in order to find a file such as a texture, the tools need to look in up to four different places, including scanning through PAK files containing thousands of files. I decided that it would be fairly straightforward to get rid of the necessity of scanning for files more than once: the tools now scan through all the places textures could be as they start up, and store the locations of the files in a hashtable, along with the file pointer of the PAK file they're in. So not only do I only read the header of each PAK file once, I only do a full scan once, and after that its just an O(1) lookup to find a file.
Anyway, the upshot of this all is that all the tools now compile and run without errors on Windows/Cygwin and on 64-bit Linux, and even create playable maps! Get the latest release now, and tell me about any problems you find.
Except q2rad, that is, because the default settings of q2rad are rubbish -- they leave the map totally unlit. Oh, for the ability to merge my code with ArghRad...