Depends on the sort of label. If it covers the entire disc evenly, then it's fine. If not, e.g. it's a square/rectangular label or on one side, it imbalances the mass of the disc, causing it to vibrate when rotating at high speeds in the drive, and who knows what could break then. It could come loose in the drive and damage the insides - at the speed it's rotating it, it's got quite a bit of energy to break stuff if it hits something. Plus because it's imbalanced, it's pulling the rotating mechanism outwards too, much like if you try spinning something on an end of a string really fast, so you could break the machanism that way. Not to mention it adds strain to the motor due to the extra force required to rotate the disc as the centre of mass is shifted away from the centre of the disc where the rotating force is applied, so you could burn the motor out too. Either that, or it simply won't spin at the required speed it needs to be spinning at since the motor isn't strong enough, so may not play correctly. This would apply to any CD/DVD, and not just console discs.
Regardless, if you have a receipt, you should be able to return the game anyway

Otherwise, I dunno, go to the police and say they're doing bad business practices or something - I'm not a lawyer, so dunno if that'd work
