Comment 40 for bug 1270656

With my laptop the problem is gone using my self compiled kernel or the latest one from Ubuntu. It is there using some older kernels. I had to carefully adjust "vga=xxx" to switch to the very same mode than gfxpayload set to 1280x800@32. Took some time and playing around until it worked as expected.
After compiling in all deprecated mode-switching stuff into the kernel I didn't have any problems any more. Looks a lot like bugs in mode handling with the kernel and/or grub2. Even access restrictions may be the case, because I saw some non fatal warnings about write restricted warnings hushing by while the kernel initialized.
But the main point was to keep all deprecated mode-switching stuff in to have graphics work as expected -- seems there are a lot of parts within all the graphics code depending on these, breaking if they are not available.