It looks like the PSU in your Gateway was made by FSP, which means it isn't crap. You should be able to run a HD5670 or HD6670 without upgrading it. If you want to run something stronger (even if it would be bottlenecked some by your current CPU), get an Antec EA380D: http://www.newegg.com/Product/Product.aspx?Item=N82E16817371033
for $40. You can then fit a HD5770 or HD6770 into your budget.
Edit: This one is only $90 if you play the rebate game and win: http://www.newegg.com/Product/Product.aspx?Item=N82E16814102941
and comes with a free game, and looks like it exhausts at least some of its heat, which could be an issue in your cramped Gateway case.