I've spent some more time in tracking this down.

If you have a video adapter that is 3D capable and supports KMS, such as the aforementioned AMD E350 APU, you shouldn't have any issues. IF you're running some... older hardware, then this might bite you.

Here's the change that made this occur:
http://files.sllabs.com/files/long-term/screenshots/kamikazi/vmware-broken-for-lubuntu-and-this-is-the-culprit-commit.jpg

On march 16th, xserver-xorg-video-all was moved from Depends to Recommends in the xserver-xorg package.

This bug happens to us for two reasons:
One: lubuntu's seed specifies no-follow-recommends.
Two: We do not have an explicit dependency on xserver-xorg-video-all.

I propose that an explicit dependency is added in either lubuntu's seed, or in one of the metapackages, to follow suit with the rest of the crowd. They all have the packages installed, one way or another, and we are the odd-man-out.

ubuntu-mate seems to have added their explicit dependency in the vivid cycle.
edubuntu had the explicit dependency in utopic, so they never noticed.
Xubuntu does not have no-follow-recommends, so they never noticed.

The others (ubuntu+Unity, kubuntu, etc) are all primarily based on GL compositors these days, and simply barf on the simple 2D cards that most of these remaining packages support.

Specifically:
xserver-xorg-video-vmware
xserver-xorg-video-vesa
xserver-xorg-video-mga
xserver-xorg-video-cirrus
xserver-xorg-video-mach64
xserver-xorg-video-trident

MGA is required to support the Matrox G200e-compatible VGA adapter found in Nuvoton and ASPEED baseboard management controllers on various supermicro X8 and X9 series motherboards.
Mach64 is required to support some older supermicro X7-series on-motherboard VGA adapter.
cirrus and trident are required for some emulation environments like qemu.

Most of the pieces of actual hardware that these drivers were built for are no longer used; but they are old enough to be "the popular virtual devices to emulate".

I am not sure if these drivers will ever be updated to support DRM or KMS, or even if it is worth it for them to be changed, with the progress on wayland+pixman.

This comment is found in several of the seeds, and no longer seems to apply as of the march 16th commit to xserver-xorg.
# this includes xserver-xorg->xserver-xorg-{input|video}-* (no need to add specific drivers manually)

Here is my factual corroboration of the above set of opinions.

[code]
ubuntu@kamikazi-builder:~/seedfinder/seeds$ grep -r "xserver-xorg" | grep -v "xserver-xorg-input" | grep -v "dbg" | grep -v "geode"
edubuntu.utopic/desktop-gnome: * (xserver-xorg-video-all)
edubuntu.vivid/desktop-gnome: * (xserver-xorg-video-all)
kubuntu.utopic/active: * xorg # this includes xserver-xorg->xserver-xorg-{input|video}-* (no need to add specific drivers manually)
kubuntu-active.utopic/active: * xorg # this includes xserver-xorg->xserver-xorg-{input|video}-* (no need to add specific drivers manually)
kubuntu-active.vivid/active: * xorg # this includes xserver-xorg->xserver-xorg-{input|video}-* (no need to add specific drivers manually)
platform.utopic/desktop-common: * xorg # this includes xserver-xorg->xserver-xorg-{input|video}-* (no need to add specific drivers manually)
platform.utopic/installer-gtk: * xserver-xorg-core-udeb
platform.utopic/installer-gtk: * xserver-xorg-video-fbdev-udeb
platform.vivid/desktop-common: * xorg # this includes xserver-xorg->xserver-xorg-{input|video}-* (no need to add specific drivers manually)
platform.vivid/installer-gtk: * xserver-xorg-core-udeb
platform.vivid/installer-gtk: * xserver-xorg-video-fbdev-udeb
ubuntu-mate.vivid/core: * xserver-xorg
ubuntu-mate.vivid/core: * xserver-xorg-video-all

ubuntu@kamikazi-builder:~/seedfinder/seeds$ grep -r "no-follow-recommends"
lubuntu.utopic/STRUCTURE:feature no-follow-recommends
lubuntu.utopic/core: * Feature: no-follow-recommends
lubuntu.utopic/desktop: * Feature: no-follow-recommends
lubuntu.vivid/STRUCTURE:feature no-follow-recommends
lubuntu.vivid/core: * Feature: no-follow-recommends
lubuntu.vivid/desktop: * Feature: no-follow-recommends
platform.utopic/build-essential: * Feature: no-follow-recommends
platform.utopic/required: * Feature: no-follow-recommends
platform.vivid/build-essential: * Feature: no-follow-recommends
platform.vivid/required: * Feature: no-follow-recommends
ubuntu.utopic/system-image: * Feature: no-follow-recommends
ubuntu.vivid/system-image: * Feature: no-follow-recommends
ubuntu-mate.vivid/STRUCTURE:feature no-follow-recommends
ubuntu-mate.vivid/cloudtop: * Feature: no-follow-recommends
ubuntu-mate.vivid/core: * Feature: no-follow-recommends
ubuntu-mate.vivid/desktop: * Feature: no-follow-recommends
ubuntu-mate.vivid/live: * Feature: no-follow-recommends
ubuntu-mate.vivid/live:# 'no-follow-recommends' is used in the seed to prevent the following
ubuntu-mate.vivid/live:== no-follow-recommends hacks ==
ubuntu-mate.vivid/live:# software when 'no-follow-recommends' is used.
ubuntu-touch.utopic/STRUCTURE:feature no-follow-recommends
ubuntu-touch.utopic/sdk-libs: * Feature: no-follow-recommends
ubuntu-touch.utopic/touch: * Feature: no-follow-recommends
ubuntu-touch.utopic/touch-android: * Feature: no-follow-recommends
ubuntu-touch.utopic/touch-core: * Feature: no-follow-recommends
ubuntu-touch.vivid/STRUCTURE:feature no-follow-recommends
ubuntu-touch.vivid/sdk-libs: * Feature: no-follow-recommends
ubuntu-touch.vivid/touch: * Feature: no-follow-recommends
ubuntu-touch.vivid/touch-android: * Feature: no-follow-recommends
ubuntu-touch.vivid/touch-core: * Feature: no-follow-recommends

[/code]