I have a fresh install of Ubuntu 16.04.1, and I get two different paths to Cwd.pm when I run locate Cwd.pm. I get the following paths,

/usr/lib/x86_64-linux-gnu/perl/5.22.1/Cwd.pm
/usr/lib/x86_64-linux-gnu/perl-base/Cwd.pm
[download]

You seem to be missing this one,

/usr/lib/x86_64-linux-gnu/perl/5.22.1/Cwd.pm
[download]

which is provided by the libperl5.22 package. Is the libperl5.22 package installed on your system?