I think I hit on a bug in avl-tree.el on GNU Emacs 24.0.94.1
(x86_64-unknown-linux-gnu, GTK+ Version 2.24.10) of 2012-03-23.

Recipe:
emacs -q
eval:
#+BEGIN_SRC emacs-lisp
(require 'cl)
(require 'avl-tree)

(defun gen-random ()
  (loop repeat 10
        concat (char-to-string (+ ?0 (random 10)))))

(loop repeat 10
      for tree = (avl-tree-create (lambda (a b) (string< a b)))
      do (loop repeat 400
               do (avl-tree-enter tree (gen-random) (lambda (data match) match))))
#+END_SRC

Backtrace: