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.
Instead, the version of Redland on the current Debian (11th September 2005) is version 18.104.22.168, so you need to download the redland-bindings for 22.214.171.124 on librdf.org, and compile them yourself by running
perl Makefile.PL and
make test and finally
You should now be able to use the RDF::Redland modules successfully.