What version of kicad are you running?
Did you create the schematic yourself? If not is it possible that the original designer either used a different release of the official libs or specialized libs for that one project that you need to add to your installation?
Is the lib you are expecting to be found part of the official libs or is it one of your personal lib? (Is the lib in the fp lib table?) If it is a personal lib, this post about creating a fp lib from scratch might have some info for you.
For the official footprint libs, kicad version 4 does use on demand online libs. This does not work if you are behind a proxy. You can install local libs. More details see the faq entry about installing footpirnt libs
It might also be a good idea to read the faq post concerning footprint assignment As it might be necessary to re assign some of your footprints if you don’t have access to the same libs as the original designer.