Hmm, interesting. I see that code gets borked if $Config{installsitearch} wasn't used. That raises a question why, of course, and which setup did you use (so I could reproduce), but generally I agress, path in %INC is more reliable. Would you try this?

--- Makefile.PL 2011-05-17 13:50:41.988807409 +0200
+++ Makefile.PL.0       2011-06-10 09:49:56.579743052 +0200
@@ -1486,8 +1486,10 @@
                unless ( $@) {
                        print "yes\n";
                        $have_binary_prereq++;
-                       push @LIBPATH, qd("$Config{installsitearch}/Pr
+ima/codecs/$prereq/lib");
-                       push @INCPATH, qd("$Config{installsitearch}/Pr
+ima/codecs/$prereq/include");
+                       my $f = $INC{"Prima/codecs/$prereq.pm"};
+                       $f =~ s/.pm$//;
+                       push @LIBPATH, qd("$f/lib");
+                       push @INCPATH, qd("$f/include");
                } else {
                        print "no\n";
                }
[download]

And btw, really, perlmonks interface doesn't help with communication at this point. Please use email next time.