I had the same problem on one of my machines. I still don't know why this one refused to detect the instant client. I got it to work by compiling with "perl Makefile.PL -l". The -l option tells the compiler to try to link to libclntsh directly.