This had me fooled for a few hours, so I thought i’d just record it here incase anyone else is having the same problem.
When installing the RDF::Redland Perl modules to use Dave Beckett’s Redland on Debian with a custom compiled version of Perl, the libraries on CPAN will not work.
Instead, the version of Redland on the current Debian (11th September 2005) is version 1.0.0.2, so you need to download the redland-bindings for 1.0.0.2 on librdf.org, and compile them yourself by running perl Makefile.PL and make, make test and finally make install.
You should now be able to use the RDF::Redland modules successfully.