missing dependencies for networking

Why has aptitude removed bridge-utils and uml-utilities?
Because they did not appear to be necessary anymore?

Yes

This bug was fixed in the package virtualbox-ose - 1.5.4-dfsg-4ubuntu2

---------------
virtualbox-ose (1.5.4-dfsg-4ubuntu2) hardy; urgency=low

  [ Saïvann Carignan ]
  * Fix deprecated values in desktop file (LP: #196714)

  [ Daniel Hahler ]
  * debian/control: Suggest bridge-utils and uml-utilities (LP: #154305)

 -- Daniel Hahler <email address hidden> Fri, 29 Feb 2008 02:26:49 +0100

According to the Debian bug report, uml-utilities is not required, nor suggested anymore.
See section "6.5.1.1 Debian and Ubuntu hosts" in the virtualbox user manual (available e.g. from http://www.virtualbox.org/wiki/Downloads).
I will remove the suggestion in the next upload.

This bug was fixed in the package virtualbox-ose - 1.5.6-dfsg-2ubuntu1

---------------
virtualbox-ose (1.5.6-dfsg-2ubuntu1) hardy; urgency=low

  * Merge from Debian unstable (LP: #202727). Remaining Ubuntu changes:
    - Move virtualbox-ose-modules from recommends
      to depends for virtualbox-ose. We can drop this change when Synaptic
      installs recommended packages by default.
    - Fix deprecated values in desktop file (LP: #196714)
    - Change Maintainer to Ubuntu MOTU Developers.
  * debian/virtualbox-ose.vboxdrv.init, debian/rules:
    Move init script from virtualbox-ose-modules to here (LP: #200380).
    This also makes sure that the udev rule to handle permissions of
    /dev/vboxdrv is installed, when this init script to modprobe the
    module is run (LP: #147076).
    debian/control: Add Breaks for virtualbox-ose-modules* meta packages
    (<< 17)
  * debian/control: virtualbox-ose-guest-utils depends on
    virtualbox-ose-guest-modules, instead of "recommends". The "vboxadd"
    module is required by the guest-utils init script (LP: #189444).
    This is also in line with the Depends for virtualbox-ose on the vboxdrv module.
  * debian/control: Drop "suggest uml-utilities" for virtualbox-ose again
    (LP: #154305)
  * Fixes the following bugs in Ubuntu:
    - Clearer message about losing snapshots during upgrade (LP: #187082)
    - virtualbox-ose conditionally modprobes vboxdrv
      (from virtualbox-ose-modules) in its init script, so that the
      modules do not need any init scripts anymore (LP: #200380)

virtualbox-ose (1.5.6-dfsg-2) unstable; urgency=low

  [ Daniel Baumann ]
  * Added Brazilian-Portuguese debconf translation from Eder L. Marques
    <email address hidden> (Closes: #467452).

  [ Michael Meskes ]
  * Added patch by Frans Pop <email address hidden> to make modules compile with
    kernel 2.6.25, closes: #468864
  * Suggest bridge-utils which is needed for static host networking.
  * Added patch against init script to remove newly created file again on
    failure, closes: #468419
  * Fixed watch file to cope with -1 upstream release.

virtualbox-ose (1.5.6-dfsg-1) unstable; urgency=low

  [ Michael Meskes ]
  * New upstream version
  * Fixed LSB headers in init.d scripts, closes: #466311
  * list x11config.pl with correct path in README file, closes: #466621
  * Added last changes made by the translation projects, thanks to
    Christian Perrier <email address hidden>.
  * Tweaked dfsg-free target in rules file so it is really executable, first
    steps made by Hilko.

  [ Hilko Bengen ]
  * Make module loading in initscript configurable (disabled by default).

  [ Patrick Winnertz ]
  * prevent initscript from failing if module doesn't exist. (Closes: #466851)

virtualbox-ose (1.5.4-dfsg-5) unstable; urgency=low

  [ Daniel Baumann ]
  * Again removing reimported useless whitespaces at EOL and EOF in debian/*.
  * Unified headers of debconf template translations.
  * Rediffed patches and again fixed their headers.
  * Added Portuguese debconf translation from Ricardo Silva <email address hidden>
    (Closes: #464761).
  * Removed extra whitespace in maintainer field of control, thanks to
    Christoph Be...