試した環境は以下の通り
VirtualPC 6.0.156.0
Debian Lenny 最小のCDイメージ バージョンは5.0.3
↓のサイトとかを参考にするとどうやらインストール時にパラメータを追加しないといけないらしいので
http://hiro-system.blog.ocn.ne.jp/blog/2009/03/debian_lennyvir_5b2e.html
インストール時にquit を取ってから"noreplace-paravirt vga=791 clock=pit"を追加する
（インストール時はまだ日本語配列ではないので=イコールのタイプには注意する）
参考リンクには/boot/grub/menu.lstを編集、update-grubするようなことが書いてあるけどなんかインストール時に指定したパラメータが有効になって既にmenu.lstに反映されていたので省く。あとGUIも使わないのでそこら辺も無視した。
参考リンク
Debian Wiki