@mattidallama, I had an Athlon 64 X2 4200+ with an HD 3870 and Bioshock ran without a hitch on high details @ 1280x1024.
@divertech, overclocking won't necessarily help a PC that is locking up. That is a sign of something else going on.
Any of the new CPUs (intel or amd) would work fine. The AMD Phenom II's are better for gaming than the Athlon IIs. Plus, AMDs are cheaper and can still run the latest games without a hitch.