Bug#41038: apt: apt-get says incorrect dependency

[Hiroshi KISE <fuyuneko@ryukyu.ne.jp>]

Package: apt
Version: 0.3.11

I try to install liburi-perl using apt-get, apt-get says
`libmime-base64-perl is not installed'.  But libmime-base64-perl is
already installed.  apt-get should say:

  liburi-perl: Depends: perl but it is not installed


------------------------( C U T   H E R E )---------------------------
# apt-cache showpkg liburi-perl
Package: liburi-perl
Versions: 1.03-1(/var/state/apt/lists/debian.softagency.co.jp_debian_dists_potato_main_binary-i386_Packages),1.01-1(/var/state/apt/lists/ftp.TokyoNet.AD.JP_pub_Linux_debian_dists_potato_main_binary-i386_Packages),
Reverse Depends: 
  libwww-perl,liburi-perl
  netscape-base-ja-4,liburi-perl
  netscape-base-4,liburi-perl
  libwww-perl,liburi-perl
  debiandoc-sgml,liburi-perl
  dailyupdate,liburi-perl
Dependencies: 
1.03-1 - perl (2 5.004) libmime-base64-perl (0 (null)) libnet-perl (0 (null)) data-dumper (0 (null)) libwww-perl (2 5.41) libwww-perl (3 5.41) 
1.01-1 - perl (2 5.004) libmime-base64-perl (0 (null)) libnet-perl (0 (null)) data-dumper (0 (null)) libwww-perl (2 5.41) libwww-perl (3 5.41) 
Provides: 
1.03-1 - 
1.01-1 - 
Reverse Provides: 
# dpkg -l libmime-base64-perl perl
Desired=Unknown/Install/Remove/Purge
| Status=Not/Installed/Config-files/Unpacked/Failed-config/Half-installed
|/ Err?=(none)/Hold/Reinst-required/X=both-problems (Status,Err: uppercase=bad)
||/ Name            Version        Description
+++-===============-==============-============================================
ii  libmime-base64- 2.11-2         MIME/Base64 decoding for Perl
pn  perl            <none>         (no description available)
# apt-get install liburi-perl
Reading Package Lists... Done
Building Dependency Tree... Done
Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.

Since you only requested a single operation it is extremely likely that
the package is simply not installable and a bug report against
that package should be filed.
The following information may help to resolve the situation:

Sorry, but the following packages have unmet dependencies:
  liburi-perl: Depends: libmime-base64-perl but it is not installed
E: Sorry, broken packages
------------------------( C U T   H E R E )---------------------------

Packages version:
ii  apt             0.3.11         Advanced front-end for dpkg
ii  libc6           2.1.1-12       GNU C Library: Shared libraries and timezone
ii  libstdc++2.9-gl 2.91.66-2      The GNU stdc++ library (EGCS version)
rc  dpkg-dev        1.4.1.3        Package building tools for Debian Linux