I've got the book (Programming the Perl DBI, Descartes & Bunce). Notice it's about DBI; I'd suggest using it if you can at all (I converted a project from using AnyDBM to MySQL and it saved me about 50% of the code and 90% of the headache).

That said, if you're still stuck with DBMs, use Berkeley DB if at all possible; the rest just plain suck for anything more than pure hash usage. Grab DB_File from CPAN and see if you can just drop in the .pm; it sometimes works without a make. At least one of the others comes with perl, and they're pretty similar feature-wise. AnyDBM just uses one of these(from perldoc AnyDBM_File, the search order is ndbm, db_file, gdbm, sdbm, odbm), so you must have one of those five.

Like btrott wrote, the $DB_HASH, $DB_BTREE, and $DB_RECNO formats are only supported by DB_File. I don't think you were trying (I did, I'll save you the pain of figuring it out :), but the neat trick the book has of using $DB_BTREE with R_DUP to allow duplicate keys doesn't work with anything other than DB_File.