Before you get too hasty and run out and buy another power supply or new memory, I would like to make a few suggestions since you didn't mention having both a CDRW and a DVD and several hard drives on your system. I know that not being able to play games when I wanted to in the past made me want to throw a fit.
Since you changed the video card from Nvidia to ATI, my guess is that your problem is a) likely with the chipset of your motherboard, b) possibly a problem with your video card driver, c) a problem in your BIOS (basic input-output system).
Download a program called Sisoft Sandra--it is a good diagnostic tool--it will tell you many things about your computer including the various manufacturers (besides Gateway), the chipset, the CPU speed, and driver versions, etc. It'll also give you suggestions on what could be wrong and what you might do to improve performance. Go to the link to download it. It's shareware, so you can't use *all of the components in the program unless you cough up $30, but the parts that are *free will tell you plenty:
http://download.cnet.com/downloads/0-10 ... ml?tag=upd
If your chipset is from VIA, you might have a chipset like the KA133, KT133, KT133A, or KT266, maybe even the KT266A (which is doubtful since Gateway is stingy and that chipset is brand new and works well). VIA has tended to have problems with their AGP and memory controllers in their chipsets so getting the newest 4-in-one drivers might help. That 4 driver package will upgrade all the software related with your chipset. If your chipset is the AMD 760, get the latest drivers from AMD. I would bet that you don't have the AMD 760 chipset though--that chipset is relatively problem free. If your chipset is from ALi or from SIS, check those sites and get updates.
Find out (using the Sandra program) who the motherboard manufacturer is and go to their website. Often times, people who have similar system setups (and therefore similar problems) will have already gone to the manufacturer's website and complained. There are usually FAQ's (frequently asked questions) that might suggest BIOS flashing (*if necessary!!*) or other suggestions to fix the problem--or they might even shed light on what the source of this problem might be, even if they don't give you the answer. DON'T FORGET TO GO TO GATEWAY!! It sounds like this should be their burden to fix, since you paid up the yin-yang for their tech support.
You mentioned that you did manage to download a lot of drivers. Was this for just hardware or did these include game patches and updates? Those are important too. I won't even play a new game till I have the patch downloaded and ready to fix the game right after I install it on the hard drive. You did mention however, that this lock-up problem affects every game that you play, so I would guess that that might not be it.
Don't forget to download the latest ATI drivers too. ATI has been known to have slow and terrible driver support for their cards in the past. Upgrade that driver too!
Also, like the other person mentioned--tinker with your video settings. Go to Start-->Settings-->Control Panel. Click on the Display icon. Click the Settings tab. Click on the Advanced button. Look for anti-aliasing (you won't see Quincunx because that is Nvidia only). Try checking-unchecking boxes and alternately starting the game that gives you the worst problems. Look to see what your OpenGL settings are set at. Mess with those too. You can tinker with these video settings freely for the most part (but do NOT change the refresh rate higher than your monitor can actually support--you could blow the tube. Rest assured though--refresh rate has nothing to do with this problem).
If the problem is in your BIOS, I suggest reading this article from Tom's Hardware. They give great tips and info (better than I can):
http://www6.tomshardware.com/howto/01q3/010725/
Finally, and maybe most importantly--make sure your OS (Windows ME) is updated. I've heard so many horror stories about that operating system, it makes one want to cry themself to sleep. Get updates!
No one person is going to have the magic bullet that will make this problem go away for you. It is up to you to find the problem for yourself.
In the end, even if this problem is indeed your power supply or memory, at least you will know that much more about how computers work and the next computer you get, you might build for yourself.
By the way, I *should tell you that 250 Watts of power is borderline and iffy. AMD (the company that makes the Athlon) recommends 300 Watts for a system running an Athlon processor, regardless of the periperals (like IDE drives, HDD, CD, DVD, and SCSI parts, etc.) Having stong and clean power to your parts is ideal but some problems wouldn't go away even if you hooked your system to a nuclear power plant. Keep the power-problem possibility in mind, though.
Keep us posted on your progress!!