Does 'nothing started' mean no fans spin, hard drives don't spin, no activity lights on the cdrom? If so, it sounds like a PSU problem. If it's got a 115/230 voltage switch make sure it's in the correct position. Make sure the PSU-to-motherboard connection is tightly installed.
Or does it mean the fans and drives spin up but no posting screen? Do you get any beeps? Remove the memory stick. Do you get any beeps now? You'd normally get some 'memory error' beeps if there's a problem with the memory or it's not there. If you get no beeps the problem is probably not with the memory stick. Make sure any cards are firmly seated. You may want to remove all except the video card and see if things improve.
I'd suggest removing and reinstalling the cpu but if you got into this much trouble with just removing the memory stick it's probably best to wait on doing anything with the cpu.
While inside the case did you remove and then reattach any data cables? If so, make sure they're reconnected correctly. Or temporarily disconnect them and see if anything improves when you boot up.
If you get beeps, check the code:
http://www.pchell.com/hardware/beep...
Your gateway probably has a phoenix bios.
It's probably best to remove and reinstall the memory. Clean the slot with compressed air to remove any dust. Make sure the memory stick contacts are clean. The stick will only fit in one way but it's possible to jam it in backwards and have it almost seem to be in correctly. So make sure the notch in the stick matches with the raised tab in the memory slot.