I just solved a similar issue. The available documentation is pretty fragmented, but there are a few consistent points. In my case, it was fixed by passing an option to the video card.
Please post the make and model of the laptop and the video card.
Also post the relevant entry in /boot/grub/menu.lst (If you have a standard installation where the bootloader was installed by Ubuntu, it will be the first entry, and will have the general form of:
kernel /boot/vmlinuz ...........
initrd (not always used)