I'm having a similar problem. Without editing the boot entry to "set gfxpayload=text" I can't boot into X. Short after the boot both my monitors don't show any video signal, I get only to see a glimpse of the text messages from booting. I can only login from remote (ssh) to reboot. I've an "ATI Technologies Inc RV670PRO [Radeon HD 3850]" and I'm using the open-source Xorg driver (if it's important). I also use "GRUB_GFXMODE=1280x1024" but the few experiments I did with "GRUB_GFXMODE=640x480" didn't show any difference. I'm currently using kernel 2.6.35-7-generic (AMD64).

Looking at the syslog for the problematic boot I see:

Jul 15 09:34:19 vorlon kernel: [   16.910054] radeon 0000:02:00.0: GPU lockup CP stall for more than 1000msec
Jul 15 09:34:19 vorlon kernel: [   16.910058] ------------[ cut here ]------------
Jul 15 09:34:19 vorlon kernel: [   16.910083] WARNING: at /build/buildd/linux-2.6.35/drivers/gpu/drm/radeon/radeon_fence.c:235 radeon_fence_wait+0x365/0x3d0 [rade
on]()
Jul 15 09:34:19 vorlon kernel: [   16.910085] Hardware name: M56S-S3
Jul 15 09:34:19 vorlon kernel: [   16.910087] GPU lockup (waiting for 0x00000002 last fence id 0x00000001)
Jul 15 09:34:19 vorlon kernel: [   16.910088] Modules linked in: snd_hda_codec_atihdmi vga16fb vgastate snd_hda_codec_realtek radeon ttm ppdev drm_kms_helper snd_
hda_intel lp snd_hda_codec drm snd_seq_midi snd_hwdep psmouse serio_raw snd_rawmidi snd_pcm snd_seq_midi_event snd_seq snd_timer snd_seq_device parport_pc parport
 i2c_algo_bit snd soundcore snd_page_alloc i2c_nforce2 k8temp edac_core edac_mce_amd raid10 raid456 async_pq async_xor xor async_memcpy async_raid6_recov raid6_pq
 async_tx raid1 raid0 firewire_ohci firewire_core multipath ahci crc_itu_t forcedeth pata_amd libahci linear
Jul 15 09:34:19 vorlon kernel: [   16.910119] Pid: 1076, comm: Xorg Not tainted 2.6.35-7-generic #12-Ubuntu
Jul 15 09:34:19 vorlon kernel: [   16.910121] Call Trace:
Jul 15 09:34:19 vorlon kernel: [   16.910128]  [<ffffffff8105f6ef>] warn_slowpath_common+0x7f/0xc0
Jul 15 09:34:19 vorlon kernel: [   16.910131]  [<ffffffff8105f7e6>] warn_slowpath_fmt+0x46/0x50
Jul 15 09:34:19 vorlon kernel: [   16.910144]  [<ffffffffa02d64d5>] radeon_fence_wait+0x365/0x3d0 [radeon]
Jul 15 09:34:19 vorlon kernel: [   16.910148]  [<ffffffff8107e4d0>] ? autoremove_wake_function+0x0/0x40
Jul 15 09:34:19 vorlon kernel: [   16.910160]  [<ffffffffa02d6cd1>] radeon_sync_obj_wait+0x11/0x20 [radeon]
Jul 15 09:34:19 vorlon kernel: [   16.910168]  [<ffffffffa00f51b3>] ttm_bo_wait+0x103/0x1c0 [ttm]
Jul 15 09:34:19 vorlon kernel: [   16.910182]  [<ffffffffa02ed927>] radeon_gem_wait_idle_ioctl+0x97/0x140 [radeon]
Jul 15 09:34:19 vorlon kernel: [   16.910197]  [<ffffffffa020035a>] drm_ioctl+0x34a/0x4c0 [drm]
Jul 15 09:34:19 vorlon kernel: [   16.910200]  [<ffffffff811e6de9>] ? ext4_file_write+0x39/0xb0
Jul 15 09:34:19 vorlon kernel: [   16.910215]  [<ffffffffa02ed890>] ? radeon_gem_wait_idle_ioctl+0x0/0x140 [radeon]
Jul 15 09:34:19 vorlon kernel: [   16.910218]  [<ffffffff8116159d>] vfs_ioctl+0x3d/0xd0
Jul 15 09:34:19 vorlon kernel: [   16.910221]  [<ffffffff81161e71>] do_vfs_ioctl+0x81/0x340
Jul 15 09:34:19 vorlon kernel: [   16.910224]  [<ffffffff81151642>] ? vfs_write+0x132/0x1a0
Jul 15 09:34:19 vorlon kernel: [   16.910226]  [<ffffffff811621b1>] sys_ioctl+0x81/0xa0
Jul 15 09:34:19 vorlon kernel: [   16.910230]  [<ffffffff8100a0f2>] system_call_fastpath+0x16/0x1b
Jul 15 09:34:19 vorlon kernel: [   16.910232] ---[ end trace ddb0eaeaf3e709e1 ]---
Jul 15 09:34:19 vorlon kernel: [   16.910239] [drm] Disabling audio support
Jul 15 09:34:19 vorlon kernel: [   16.911294] radeon 0000:02:00.0: GPU softreset 
Jul 15 09:34:19 vorlon kernel: [   16.911296] radeon 0000:02:00.0:   R_008010_GRBM_STATUS=0xA0003030
Jul 15 09:34:19 vorlon kernel: [   16.911299] radeon 0000:02:00.0:   R_008014_GRBM_STATUS2=0x00000003
Jul 15 09:34:19 vorlon kernel: [   16.911301] radeon 0000:02:00.0:   R_000E50_SRBM_STATUS=0x200208C0
Jul 15 09:34:20 vorlon kernel: [   17.059526] radeon 0000:02:00.0: Wait for MC idle timedout !
Jul 15 09:34:20 vorlon kernel: [   17.059529] radeon 0000:02:00.0:   R_008020_GRBM_SOFT_RESET=0x00007FEE
Jul 15 09:34:20 vorlon kernel: [   17.074542] radeon 0000:02:00.0: R_008020_GRBM_SOFT_RESET=0x00000001
Jul 15 09:34:20 vorlon kernel: [   17.090555] radeon 0000:02:00.0:   R_008010_GRBM_STATUS=0x00003030
Jul 15 09:34:20 vorlon kernel: [   17.090558] radeon 0000:02:00.0:   R_008014_GRBM_STATUS2=0x00000003
Jul 15 09:34:20 vorlon kernel: [   17.090560] radeon 0000:02:00.0:   R_000E50_SRBM_STATUS=0x200208C0
Jul 15 09:34:20 vorlon kernel: [   17.091561] radeon 0000:02:00.0: GPU reset succeed
Jul 15 09:34:20 vorlon kernel: [   17.093129] [drm] Clocks initialized !
Jul 15 09:34:20 vorlon kernel: [   17.241969] radeon 0000:02:00.0: Wait for MC idle timedout !
Jul 15 09:34:20 vorlon kernel: [   17.391453] radeon 0000:02:00.0: Wait for MC idle timedout !
Jul 15 09:34:20 vorlon kernel: [   17.575352] [drm:r600_ring_test] *ERROR* radeon: ring test failed (scratch(0x8504)=0xCAFEDEAD)
Jul 15 09:34:20 vorlon kernel: [   17.575357] [drm:r600_resume] *ERROR* r600 startup failed on resume