--- 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
@@ -2034,7 +2034,7 @@ bool DoInstall(CommandLine &CmdL)
 	 regfree(&Pattern);
 	 
 	 if (Hit == false)
-	    return _error->Error(_("Couldn't find package %s"),S);
+	    return _error->Error(_("Couldn't find package %s"),OrigS);
       }
       else
       {