Быстрый patch, который помог - было 
E: Couldn't find package perl(Test
стало
E: Couldn't find package perl(Test/More.pm)>=0.01

№------------------------------------
--- a/apt/cmdline/apt-get.cc
+++ b/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
№------------------------------------
В коде 2 сообщения Невозможно найти пакет...
возможно, имеет смысл запатчить оба, как в расширенном патче внизу.
--- a/apt/cmdline/apt-get.cc
+++ b/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
       {

Created attachment 5470 [details]
simple patch that work

simple patch that work

Created attachment 5471 [details]
extended patch

Расширенный патч.
Там два места, где выводится сообщение, 
по идее оба надо пропатчить.

Прошу приложить предложенный патч.

apt-0.5.15lorg2-alt41 -> sisyphus:

* Thu May 24 2012 Dmitry V. Levin <ldv@altlinux> 0.5.15lorg2-alt41
- apt-get, apt-shell: when a package could not be found, print the
  unmangled package request string (by Igor Vlasenko; closes: #27364).
- apt-shell: do not abort when commit is cancelled (closes: #13877);
  Unlike one may suppose, this change will not cause the cache of
  accumulated changes to be cleared by cancelled "commit" operation, but
  this is exactly what Vitaly Lipatov has proposed in his comments to #13877.

Thanks!