The TwoLevels backend doesn't correctly update the fast cache, if it's full. Attached unit test shows the problem.

Two possible solutions:

1. update fast if entry exists ignoring usage. (Assuming the old and new data will have similar size)

Index: Zend/Cache/Backend/TwoLevels.php
===================================================================
--- Zend/Cache/Backend/TwoLevels.php    (revision 21942)
+++ Zend/Cache/Backend/TwoLevels.php    (working copy)
@@ -174,7 +174,7 @@
         $boolFast = true;
         $lifetime = $this->getLifetime($specificLifetime);
         $preparedData = $this->_prepareData($data, $lifetime, $priority);
-        if (($priority > 0) && (10 * $priority >= $usage)) {
+        if ((($priority > 0) && (10 * $priority >= $usage)) || $this->_fastBackend->test($id)) {
             $fastLifetime = $this->_getFastLifetime($lifetime, $priority);
             $boolFast = $this->_fastBackend->save($preparedData, $id, array(), $fastLifetime);
         }

1. when updating and an entry exists remove it

Index: Zend/Cache/Backend/TwoLevels.php
===================================================================
--- Zend/Cache/Backend/TwoLevels.php    (revision 21942)
+++ Zend/Cache/Backend/TwoLevels.php    (working copy)
@@ -177,6 +177,8 @@
         if (($priority > 0) && (10 * $priority >= $usage)) {
             $fastLifetime = $this->_getFastLifetime($lifetime, $priority);
             $boolFast = $this->_fastBackend->save($preparedData, $id, array(), $fastLifetime);
+        } else if ($this->_fastBackend->test($id)) {
+            $this->_fastBackend->remove($id);
         }
         $boolSlow = $this->_slowBackend->save($preparedData, $id, $tags, $lifetime);
         return ($boolFast && $boolSlow);

(Included in the unit test patch is a change to the TwoLevels backend constructor that allows giving slow and fast backend directly as objects, just like Zend_Cache::factory does. This made it easier to write the test using a mock object)