Bug#29767: apt-get confused by nested/repeated OR (|)?

[Jeroen Nijhof <J.H.B.Nijhof@aston.ac.uk>]

Package: apt
Version: 0.1.9

If I try to install libfnlib0 it complains about unmet dependencies
-- libgif3g -- but in the shown chain the dependency is always
libungif3g | libgif3g, and libungif3g is installed:

penguin:~# apt-get -s install libfnlib0

Updating package status cache...done
Checking system integrity...ok
1 packages upgraded, 0 newly installed, 0 to remove and 0 not upgraded.
Sorry, but the following packages are broken - this means they have unmet
dependencies:
  libfnlib0: Depends:imlib1 Depends:giflib3g

--- 
dpkg --print-avail libfnlib0 :
Depends: [..], imlib1 (>= 1.6), [..], 
     libungif3g (>= 3.0-2) | giflib3g (>= 3.0-5.2), [..]

dpkg --print-avail imlib1 :
Depends: [..], libungif3g (>= 3.0-2) | giflib3g (>= 3.0-5.2), [..]

dpkg -l imlib1 libungif3g :
ii  imlib1          1.8.1-0.1      Imlib is an imaging library for X and X11
ii  libungif3g      3.0-2          shared library for GIF images (runtime lib)

Jeroen Nijhof