My first description wasn't quite accurate.  What was happening is that
the __delitem__(i) call by del was closing the existing cursor and
saving the key it was pointing to and the first() and last() methods
were creating a new cursor and trying to restore the new cursor to the
last known position saved when __delitem__ closed the previous cursor. 
This failed as that item no longer existed.  first() and last() by their
very nature don't need to restore the cursor position since they set it
to an absolute position.  Here's the patch to fix this:

--- Lib/bsddb/__init__.py       (revision 57289)
+++ Lib/bsddb/__init__.py       (working copy)
@@ -274,12 +274,16 @@
 
     def first(self):
         self._checkOpen()
+        # fix 1725856: don't needlessly try to restore our cursor position
+        self.saved_dbc_key = None
         self._checkCursor()
         rv = _DeadlockWrap(self.dbc.first)
         return rv
 
     def last(self):
         self._checkOpen()
+        # fix 1725856: don't needlessly try to restore our cursor position
+        self.saved_dbc_key = None
         self._checkCursor()
         rv = _DeadlockWrap(self.dbc.last)
         return rv