From what I heard, this "rule" was proposed by lawyers who studied this exact type of issue. It is applied in at least 1 videogame company that I know of.
I also know an Art Director who confirmed me that's what they were told at the university actually.
Also, the rule don't make sense if you apply a non-logical reflection to it, nemo. :)
Changing the color of half of Mario's body is not modifying 50% of its appearance. I would guess about 10%.
You would need to, example, change the colors AND his apparels (say for a t-shirt and jeans) make him taller, replace his cap for hair, remove the mustache. That counts for at least 50% changes, therefore, from what I heard, would constitute a new design that you would own the rights to.
It's just there's no legal document that I can find or article on the internet confirming it.
Another interrogation I have: Can you use the image of a popular building freely in a game? Or do you need to ask the city in which it resides for permission? I'm going to do some research about that right now. :)