They can refuse to exchange it for a different item, but they can not legally refuse to replace a defective product. If they accepted a re-sealed product back as new, they can not sell it and basically say 'you touched it last, it's yours'.
For all the BS they can try on the phone, just show up, explain how you installed the game on two different computers and got the same disk error, and that the disk is defective.
Wallmart has the most liberal return policy around. Managers may complain about copyrights, etc, the person actually at the returns desk may not be quite so picky (in fact I've known some to be extremely un-picky). Also, while you certainly want to start off polite, on the phone they don't really care if you get angry and raise your voice; in the store it's a different situation.