VirtualBox の Forum を見ると、動かないぞ という情報が見つかりました。

DOA - I upgraded from SL to Lion and existing VM's wont start. Reinstalled virtualbox, still no love.

しかし、VT-x 設定を Disable にすれば動作するようです。また、これは Kernel 32bit の Mac で発生するようで 64bit では動作するとのこと。

Found a posted workaround. Disable VT-x in the VMs: Settings -> System -> Acceleration

It appears to not work under K32, make sure you are booted into K64

さらに色々と調べてみると、VirtualBox の Change log の 4.0.10 にこの問題の修正と思われる記述がありました。

・ Mac OS X hosts: Lion fixes (bug #8903)

うちの iMac は kernel 64bit で動かしているし、VirtualBox も最新の 4.0.10 にしているので、とりあえずは動作しそうです。一安心。

調べているついでに、以下のような記事も見つけました。
Full-screen-app support coming in Mac OS X Lion

どうやら、OS X Lion 新機能のひとつである フルスクリーンアプリケーション にも対応予定とのこと。
これは楽しみですね。VirtualBox で Windows ゲストをフルスクリーンアプリとして使えば、あたかも Windows マシンであるかのように見えて、他の Mac アプリケーションに切り替えるには３本指のスワイプで OK となると、使い勝手がさらに良くなりそうです。