Which would work better for gaming paired with this GPU?

Either if OC the Phenom a little it will game as well as the i3

If this is more than just a gaming machine then the Phenom

the quad core would be slightly better but it will need over clocking to make sure you limit any chance of a bottleneck.
the problem with this choice is theres very little between them the i3 will work as well if not better on some games but the quad will work better on games that benefit from 4 true cores like bf3
the i3 is the better buy in that you can always throw in a i5 later with no hassle but the quad will give the performance out the box and will last at least 2 years b4 it needs or maybe wants upgrading.(depends on the consoles and whats inside em).
but for this build i would say the amd quad...

I concure with Hexit. Check out some stats here...
http://www.anandtech.com/bench/CPU/50
The i3 is more dominant but is not a true quad. It will probably be weaker on games where a quad is required like bf3.
If you can stretch yourself to the i5.