I don't understand why people get a pre-built pc and then proceed to replace half the compnents(GPU, PSU, CPU, etc.). IF you are doing that then why not just build your own in the first place.
As for your question, it is indeed difficult to find an 810 to buy. I would say to just buy like a Phenom II 955 for like $90, but then there's the question of if it will work or not. I did some googleling but wasn't able to find much.
I'd say your best bet is to contact Gateway and inquire as to what CPU upgrades/models your motherboard supports. I believe the motherboard in that pc is a Foxconn Bengal RS780