If you're binding as the rootdn successfully, it's probably only that
given bdb backend that's faulty. Can you track down the Sleepycat library
you're using (perhaps using ldd), and find out what version it is?
At risk of my getting shot by Howard, are you caring for your Sleepycat
log files properly? DB_CONFIGs for autoremove, or are there cron jobs for
db_archive, etc.? What are your DB_CONFIGs, for that matter? (They'd have
to be pretty far off to cause this behavior, but it's a quick look at
least.)