Yes. Exactly. You have found the problem.http://support.gateway.com/s/pc/R/1009371/1009371nv.shtml
Uses an ATX form factor Power Supply. One that is common in a LOT of desktop computers. Readily available.
Gateway Support indicates there are three generic Power Supply makers, for the Power Supply in your computer,
Delta, HiPro, and Bestec. (Same one's for HP too)
Indicates the form factor is uATX/BTX.
An ATX Power Supply's case dimensions are approximately -
6 Inches Wide, 5.5 Inches Long, and 3.5 Inches Tall.
Power cabling is also a designator when referring to ATX.
The new Power Supply's on the market, cover ATX power cabling, and more.
This is an example of an economical, yet reliable, Power Supply, that will work,http://www.tigerdirect.com/applications/SearchTools/item-details.asp?EdpNo=4465483&CatId=1079
Has all the power cables you will need, plus more. Tie the unused power cables up out of the way. (USE plastic ties)
Concerned it is a 500 Watt unit, and not a 300 Watt unit as came with your computer?
No need to be.
1) A computer ONLY uses the power it needs, and NO more.
If you are surfing the internet, and the computer only needs a 100 Watts, it will ONLY use 100 Watts.
Playing an intensive game, or using an intensive program?
Could use the whole 500 Watts.
2) Will it harm your computer? No.
You could use a 10,000 Watt Power Supply, and it won't harm your computer. (10,000 Watt is an exaggeration)
Because a computer will ONLY use the power it needs, and NO more.
For additional questions please post in a Comment.