Before you do anything else - check your memory.

Download an Ubuntu Live CD. Boot it and select the mem test option.

I ALWAYS check the memory first. It causes the strangest errors. Not saying that is what is going on here but if after 5 - 10 minutes no errors pop up then keep diagnosing.

Usually errors in memory pop up instantly and the system was booting just fine, just experiencing strange errors now and again.

Also check for proper cooling - video cards can freeze like that if they over heat. Make sure there is ample airflow and there are applications out there to monitor temperatures. Nvidia and AMD should both have them. Make sure your hardware is ok first THEN check the software.