I have been living with the symptoms of #446312 for weeks on several machines and just realized today the core issue, which is already fixed upstream and contained in a new release: 21.5.8.
#467262 is also fixed in this release.
Just renaming the ebuild accordingly led to a working install for me.
While you're on it: A small typo is present in the einfo ("imporrt autojump_ipython" => "import autojump_ipython").
+*autojump-21.5.8 (04 May 2013)
+ 04 May 2013; Michael Weber <email@example.com> +autojump-21.5.8.ebuild,
+ +files/autojump-21.5.8-eprefix.patch, autojump-21.3.0-r1.ebuild:
+ Version bump (thanks Oliver Freyermuth, bug 468056), fix python-r1 support.