I get hit by a similar problem occasionally. I would definitely check the permissions on the installed module. When I install as root, I sometimes forget to drop my umask from 077 (my paranoid default) to 022 (so that non-root users can read/execute stuff installed). Also look in architecture-specific subdirectories. (i.e., at work when I mess this up, I've got to check solaris4-multi-thread, or whatever, and at home, i686-linux subdirs).
Update: The reason the error message doesn't indicate anything about reading or executing is because it couldn't find the file, as the permissions on the directory containing the .pm are too strict. Example:
# ls -ld *perm{,/A.pm}
drwx------ 2 root root 17 Jul 28 15:16 badperm
-rw------- 1 root root 48 Jul 28 15:16 badperm/A.pm
drwxr-xr-x 2 root root 17 Jul 28 15:16 goodperm
-rw-r--r-- 1 root root 49 Jul 28 15:16 goodperm/A.pm
# head *perm/A.pm | grep .
==> badperm/A.pm <==
package A; print "Here I am (badperm/A).\n"; 1;
==> goodperm/A.pm <==
package A; print "Here I am (goodperm/A).\n"; 1;
# perl -we 'BEGIN { @INC=qw/badperm goodperm/; } use A'
Here I am (badperm/A).
$ perl -we 'BEGIN { @INC=qw/badperm goodperm/; } use A'
Here I am (goodperm/A).
$ perl -we 'BEGIN { @INC=qw/badperm/; } use A'
Can't locate A.pm in @INC (@INC contains: badperm) at -e line 1.
BEGIN failed--compilation aborted at -e line 1.
