X won't start every other reboot (video mode change problem?) - Kubuntu Edgy

Kubuntu Edgy does not shut down cleanly. It tries, but after the screen clicks to change video modes nothing else ever appears. The machine does not shut down or reboot.

When I Alt+SysRq+S+U+B or pull-the-power-cord reboot it, the first time coming up it never starts X successfully (it changes video modes after briefly showing the "Kubuntu" screen, but never shows the wait cursor or subsequent login dialog). Alt+F1 does not successfully bring up a terminal. If I reboot it again, it will usually boot successfully the second time. Sometimes a third reboot is needed.

Once X is started and I can login, the system runs great and I have no video problems UNLESS I try to play SuperTux. When SuperTux starts and it changes video modes the screen often (but not always) goes black and the system freezes. I think the key thing is that it doesn't want to change video modes.

I have pored over the log files trying to figure out what the problem is and don't see it. I've attached several logs to my posting on ubuntuforums.org (http://ubuntuforums.org/showthread.php?t=329505).

The video card is an ATI All-In-Wonder 8500DV video card. I am using the open source radeon driver ("ati"), and I get nice video performance with hardware acceleration. I tried using the fglrx drivers and, when I got hardware acceleration, X would always hang when opening desktop windows so it was unusable. If I disabled hardware acceleration, video performance was very poor.

Please help!