Did you install pnp4nagios via packages or manually?
Are the paths in the pnp module settings correct? (Configuration->Modules->pnp->Config)
Afaik if you run Ubuntu 16.04 you need to install pnp4nagios manually and need to change some things compared to an Ubuntu 14.04 install:
(path might differ)
comment those lines