Index: pym/portage_checksum.py
===================================================================
--- pym/portage_checksum.py	(revision 6332)
+++ pym/portage_checksum.py	(revision 6333)
@@ -181,6 +181,7 @@
 	@rtype: Tuple
 	@return: The hash and size of the data
 	"""
+	global prelink_capable
 	myfilename      = filename[:]
 	prelink_tmpfile = os.path.join("/", PRIVATE_PATH, "prelink-checksum.tmp." + str(os.getpid()))
 	mylock          = None
@@ -189,10 +190,14 @@
 			mylock = portage_locks.lockfile(prelink_tmpfile, wantnewlockfile=1)
 			# Create non-prelinked temporary file to checksum.
 			# Files rejected by prelink are summed in place.
-			retval = portage_exec.spawn([PRELINK_BINARY, "--undo", "-o",
-				prelink_tmpfile, filename], fd_pipes={})
-			if retval == os.EX_OK:
-				myfilename = prelink_tmpfile
+			try:
+				retval = portage_exec.spawn([PRELINK_BINARY, "--undo", "-o",
+					prelink_tmpfile, filename], fd_pipes={})
+				if retval == os.EX_OK:
+					myfilename = prelink_tmpfile
+			except portage_exception.CommandNotFound:
+				# This happens during uninstallation of prelink.
+				prelink_capable = False
 		try:
 			if hashname not in hashfunc_map:
 				raise portage_exception.DigestException(hashname + \