--- a/apt/cmdline/apt-get.cc	
+++ a/apt/cmdline/apt-get.cc	
@@ -1995,7 +1995,7 @@ bool DoInstall(CommandLine &CmdL)
 	    if (Hit == true)
 	       continue;
 #endif
-	    return _error->Error(_("Couldn't find package %s"),S);
+	    return _error->Error(_("Couldn't find package %s"),OrigS);
 	 }
 
 	 // Regexs must always be confirmed