Please double check to see all of your connections are properly seated and connected properly too.
Is this your computer? Gateway Support - Specifications
If so they didn't mention what motherboard you had.
I suggest we try going bare minimum if you feel comfartable of course. I suggest you to unplug all your harddrives any anything that is extra.
Since we know the old Power supply (300W) was working before lets test this one.
Please plug in your Power supply to your motherboard.
If i am correct there should be 2 cables total.
Your motherboard will use either a 20 or 24 pinpower cable. since it seems like this computer is a bit old i think it will use 20 pin.
It should also use a 4 pin power connecter too.(Sometimes they are 8 pin)
Make sure the CPU is properly seated and locked in. Make sure the fan is also properly plug in.
I know personally from experience that if your motherboard isn't locked down properly your computer wont turn on.
Also make sure your power supply is turn on, some power supplies have an on and off switch in the back. Like always be safe and remember to be grounded. Avoid ESD (electric static discharge.
If i wasnt clear please let me know. Doing the best i can
Hoping we can solve this together