libdbmdeep-perl is obsolete, and should be replaced by libdbm-deep-perl.
The package is at version 0.94-1, in every release from Dapper to Jaunty. 0.94 was released in April of 2004, but there have been numerous releases over the intervening (almost) five years.
Debian is shipping 1.0014 under the name "libdbm-deep-perl"; it's a new packaging series (not derived from the version Ubuntu ships), and there are some concerns that need to be addressed before it's imported for Jaunty+1. Because Debian isn't shipping "libdbmdeep-perl" in any repository, and their package doesn't note that it clashes, any Ubuntu version is going to have to have a Replaces (or something like that) directive in its control file. Also, the database format has changed; there's a db_upgrade.pl script included with current versions which is used for migration, but it will make the files unreadable to older versions. I don't know how that's going to be handled, but there should at the very least be some notes in a NEWS.Debian or the like about it.