On ubuntu elib is not part of the emacs22 install (there is a separate elib package though). Do you know when it became included in emacs 22?
Emacs 23 comes with avl-tree.el (with differently named functions). Ludovic supplied a patch that lets jdee use avl-tree.el rather than elib avltree. It is available at https://svn.nixos.org/repos/nix/nixpkgs/trunk/pkgs/applications/editors/emacs-modes/jdee/elib-avltree.patch which is probably better (if we also add some emacs 22 compatibility adapters to jde-compat.el)