I've always thought it worked that magic wasn't as much a weakness as it is something that his natural durability isn't best suited to deal with. It doesn't depower him like kryptonite, but it can hurt him through his defenses where a normal "physics" based attack/weapon might not (enchanted sword vs. regular sword), and high end spells will mess with him just as they would anyone else.