I am experiencing a similar sounding problem on a Dell Inspiron 6400 with a Mobility Radeon X1400 GPU running Lucid 64bit with the 2.6.32-22 kernel. Boot will randomly freeze with red vertical lines (artifacts) at the top of the screen. When this happens the machine is *completely* frozen, i.e. cannot Ctrl+Alt+F1 to drop to a terminal, cannot even do Alt+SysRq+REISUB for a reboot. Even it thought it's random, it happens quite frequently, probably close to 50% of the time on average.
I tried booting without the splash to catch an error message but even then the screen is completely corrupted and nothing can be seen. I am running another 64bit machine with the same kernel, but Intel graphics and never experience this problem. That and the screen corruption seem to confirm that it is an ATI problem.