First find out what version of bdb (Berkely DB) slapd is using:
apt-cache show slapd
[snip]
Depends: libc6 (>= 2.4), libdb4.2, libgcrypt11 (>= 1.4.0), libgnutls26 (>= 2.4.0-0), libldap-2.4-2 (= 2.4.11-0ubuntu6), libltdl7 (>= 2.2.4), libperl5.10 (>= 5.10.0), libsasl2-2, libslp1, libtasn1-3 (>= 0.3.4), libwrap0 (>= 7.6-4~), unixodbc (>= 2.2.11-1), zlib1g (>= 1:1.1.4), coreutils (>= 4.5.1-1), psmisc, perl (>> 5.8.0) | libmime-base64-perl, adduser
[snip]
Then install the appropriate version of dbX.Y-util:
apt-get install db4.2-util
The utilities like db_recover and db_verify are actually named db4.2_verify and db4.2_recover. You can see a list with:
dpkg -L db4.2-util