Certainly, though you may want to keep an eye on your PSU. The 5450 is not a big juice sucker but it will increase the power drain on your system and as you have an older box and undoubtedly older PSU this is likely the straw that could break the camel's back. You might just want to get another new one. BTW, if you do decide to spend the extra on a new PSU, you might want to consider getting the faster more capable 5670 or 6670. Either would be better choices. In a similar vein, the 5570 is a better choice.
http://www.hwcompare.com/190/radeon-hd-5450-vs-radeon-hd-5570/
As for the CPU element, you are limited to AMD socket 939 CPUs. This page at Gateway is for your motherboard:
http://support.gateway.com/s/MOTHERBD/MSI/103171/103171sp2.shtml
It lists in a confused way the range of the 3500+ 3700+ 3800+ units as being compatible. I would take as gospel only the actual NAMED units as really working in this board. The differences between the various units is not all that great.
The 3500+ has a speed of 2.2 GHz and 512kb of L2. The 3700+ the same speed but with 1MB of L2. The 3800+ ran at 2.4 GHz but had 512kb of L2. For completions sake, the 4000+ ran at the same 2.4 GHz and had 1MB of L2. The 4000+ may well work fine in this board but then again you are on your own here due to the Gateway listing's limitations.
The performance differences between the CPUs above wouldn't be very much different, probably in the range of 10 to 15%. You would be the judge of the value of this.