This can be caused by a fair number of things. Instead of trying to Alt-Enter to get out of full screen, type "exit" at the prompt and see what happens.
I've seen it suggested often to actually go into the BIOS and tell it to set everything to default settings when this happens. Sometimes it works, sometimes it doesn't.
If it doesn't, download memtest86 and run it overnight and make sure there isn't a problem with your RAM. While RAM shouldn't directly effect this, I've seen a few cases where the RAM had errors and replacing/removing made this problem stop. Not sure why, but like I said, I've seen it reported as a cause a few times.
Another common suggested cause, as rthompson already pointed out, is flashing the BIOS or the BIOS has somehow been corrupted or changed in a way it didn't like. As a last resort, you could try downloading a BIOS update (either a new or old version) and try to overwrite the corrupted BIOS. Do this at your own risk, as I can't guarantee it will fix your problem or that it won't make it worse or kill it altogether.