It turns out that nxcomp* is built in such a way that the +x bit is missing after `make install`, which in turn leads to rpm not considering the file for dependency resolution. This should be fixed - $(INSTALL_DATA) $(LIBFULL) $(DESTDIR)${libdir}/nx + $(INSTALL_PROGRAM) $(LIBFULL) ... (for nxcomp, nxcompshad and nxcompext)