OpenLDAP Errors

I ran across the following error in OpenLDAP two weeks ago when deleting an entry:

"Additional info: entry index delete failed"

Huh? We've been using OpenLDAP since 2003 and I've never seen this problem before, but looking at the OpenLDAP code showed it was trying to delete an index. We use the BDB backend and apparently a BDB index was corrupt. I haven't found an easy way to repair these indexes besides dumping all the data and re-importing. Maybe a BDB expert out there has some suggestions but luckily we replicate all of our data across multiple machines so I just had to copy the data (zip up the /var/openldap-data/ directory) from another machine. Googling for the error above didn't return many results so I thought I would go ahead and post my findings for the next person who searches for this error.