I'd say that either some of the textures are missing, or you are looking at back faces, not front faces. The textures that are missing are ones that you did not add to the standard ones. If it is backfaces, it is a simple matter to determine that. Just texture the backfaces with an absurd color, like pink. They will stand out quite obviously if they are the back face then. Quark, and some other mapping programs do this. Then, it means that your triangles are 'wound' backwards. Front faces usually wind clockwise, backfaces, counterclockwise. (iirc) I have not had that problem in Quark, but I have had it with some converters (arrggh!) and in x-format in general. I wrote some DirectX 7 code to load and display a Quake III map, and I had that issue; it was my code's error. Whenever I import an x model into 3DCanvas, there are some holes, and it is the back face showing. If, for example you see that in Quark, then you can edit that triangle directly. I have accidentally done this in Quark before. It happens when you are editing groups, and you somehow edit the back face. The texture gets applied to the back face, and the front face is blank! So, that is another way you can get what you are seeing.
There are two ways to fix the texture problem. Either copy the textures into the pk3, in the directory textures. Or, add them into the default library in Quark, or whatever map program you use. I think a third option might be to put them in the same directory as the bsp file.
What may work better is to create an empty pk3 with the directory structure you are using already already in the pk3. Then you would add maps and textures, and it should work fine automatically.
I will spend a little time this evening attempting to create something of a framework for setting this up. It is the asset pipeline, very crucial to the game. It is vital to start with that working properly because the assets will be difficult to insert if this is not established early, and naturally the entire process becomes more frustrating in general.
Sorry to go on, but I think that is what is going on with your bsp. I think one of the things I went on about it the problem. I can almost see it! It looks like the textures from Quake II, like the very first level.