It seems that - so far - this isn't possible, at least with Ubuntu 8.10. WINE 1.0.1 and VirtualBox 2.1.0.
With VirtualBox and 2k (assigned 512MB RAM plus 128MB for graphics), the layout editor complains about a lack of available memory. VirtualBox has only recently started to support 3D acceleration for VMs, and that (so far) only under XP. KVM/Qemu doesn't support 3D acceleration (and won't as it emulates a mid-90s Cirrus Logic graphics card). Haven't tried VMWare Player, so I don't know how well that'd work.
With WINE, the installer itself runs correctly until it reaches the DirectX websetup tool, which crashes. The Visual C++ Runtime doesn't install or work correctly under Ubuntu 8.10's version of WINE, so even running the physical (XP) machine's copy of Construct does not work (after using winetricks to install DirectX).
As to which one might end up being able to support Construct first, I actually hope it's WINE (after fixing the DirectX installer problems), although either would be nice.