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 220.127.116.11, so you need to download the redland-bindings for 18.104.22.168 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.