Ok, this is actually a problem that my brothers computer is having. No spyware/viruses as far as I can tell.

Basically you can start windows but then you can't open anything. If you try to open My Computer it will give you an error message saying that there is a problem with Windows Explorer and asks you if you'd like to send an error report.

He says he's fine with just formating the hard drive and reinstalling windows, but I can't even seem to do that. Put in the recovery disk and nothing happens.

BTW when you start it up it automatically goes to a screen asking what version of windows you want to open (kinda looks like when you try to start in safe mode, except it won't let me start in safe mode...) It gives you 2 choices, but both choices are the same - Windows XP home edition

Any ideas?

blah couple of things...start->run->cmd->sfc /scannow (with xp cd in drive) might help
standard to get into safe mode is F8 at boot..
as for dual listing of OS normally seems to be a quirk after reinstalling the OS can be disabled control panel->performance and maintenace(system in classic)->system->Advanced tab->click settings button under startup and recovery. in new window should give an option of time to display operating systems at startup (or along those lines) uncheck the box... apply and ok or again along those lines (sorry not working from my xp comp)
Just generally speaking if need more help just ask

Maybe faulty ram or software error. Attach the following files here. I will study your log and dumps.
C:\Documents and Settings\All Users\Application Data\Microsoft\Dr Watson\drwtsn32.log
C:\Documents and Settings\All Users\Application Data\Microsoft\Dr Watson\user.dmp