I've been removing some of the additional @INC paths that we built into Perl to protect our environment a little, but I'll include them here, changed, for the sake of thoroughness.

[me@unixbox1:/home/me]> perl -V
Summary of my perl5 (revision 5 version 8 subversion 8) configuration:
  Platform:
    osname=solaris, osvers=2.8, archname=sun4-solaris
    uname='sunos unixbox1 5.8 generic_117350-44 sun4u sparc sunw,ultra
+-250 '
    config_args='-d -Dotherlibdirs=/home/app_1:/home/app_2 -Dinc_versi
+on_list=none -Dperladmin=brainsick@local.domain'
    hint=recommended, useposix=true, d_sigaction=define
    usethreads=undef use5005threads=undef useithreads=undef usemultipl
+icity=undef
    useperlio=define d_sfio=undef uselargefiles=define usesocks=undef
    use64bitint=undef use64bitall=undef uselongdouble=undef
    usemymalloc=n, bincompat5005=undef
  Compiler:
    cc='/opt/SUNWspro/bin/cc', ccflags ='-I/usr/local/include -D_LARGE
+FILE_SOURCE -D_FILE_OFFSET_BITS=64',
    optimize='-O',
    cppflags='-I/usr/local/include'
    ccversion='Sun C 5.7 2005/01/07', gccversion='', gccosandvers=''
    intsize=4, longsize=4, ptrsize=4, doublesize=8, byteorder=4321
    d_longlong=define, longlongsize=8, d_longdbl=define, longdblsize=1
+6
    ivtype='long', ivsize=4, nvtype='double', nvsize=8, Off_t='off_t',
+ lseeksize=8
    alignbytes=8, prototype=define
  Linker and Libraries:
    ld='/opt/SUNWspro/bin/cc', ldflags =' -L/usr/lib -L/usr/ccs/lib -L
+/opt/SUNWspro/prod/lib/v8plus -L/opt/SUNWspro/prod/lib -L/lib -L/usr/
+local/lib '
    libpth=/usr/lib /usr/ccs/lib /opt/SUNWspro/prod/lib/v8plus /opt/SU
+NWspro/prod/lib /lib /usr/local/lib
    libs=-lsocket -lnsl -ldl -lm -lc
    perllibs=-lsocket -lnsl -ldl -lm -lc
    libc=/lib/libc.so, so=so, useshrplib=false, libperl=libperl.a
    gnulibc_version=''
  Dynamic Linking:
    dlsrc=dl_dlopen.xs, dlext=so, d_dlsymun=undef, ccdlflags=' '
    cccdlflags='-KPIC', lddlflags='-G -L/usr/lib -L/usr/ccs/lib -L/opt
+/SUNWspro/prod/lib/v8plus -L/opt/SUNWspro/prod/lib -L/lib -L/usr/loca
+l/lib'


Characteristics of this binary (from libperl): 
  Compile-time options: PERL_MALLOC_WRAP USE_LARGE_FILES USE_PERLIO
  Built under solaris
  Compiled at Jan 18 2007 07:45:13
  %ENV:
    PERL5LIB="/home/me/build/perl-addons/inst/usr/local/lib/perl5:/hom
+e/me/build/perl-addons/inst/usr/local/lib/perl5/site_perl"
  @INC:
    /home/me/build/perl-addons/inst/usr/local/lib/perl5/5.8.8/sun4-sol
+aris
    /home/me/build/perl-addons/inst/usr/local/lib/perl5/5.8.8
    /home/me/build/perl-addons/inst/usr/local/lib/perl5
    /home/me/build/perl-addons/inst/usr/local/lib/perl5/site_perl/5.8.
+8/sun4-solaris
    /home/me/build/perl-addons/inst/usr/local/lib/perl5/site_perl/5.8.
+8
    /home/me/build/perl-addons/inst/usr/local/lib/perl5/site_perl
    /usr/local/lib/perl5/5.8.8/sun4-solaris
    /usr/local/lib/perl5/5.8.8
    /usr/local/lib/perl5/site_perl/5.8.8/sun4-solaris
    /usr/local/lib/perl5/site_perl/5.8.8
    /usr/local/lib/perl5/site_perl
    /home/app_1
    /home/app_2
    .
[download]

I'm still not understanding why quitting the CPAN shell and restarting it causes the module to be found.