Uhh dude that is basic copywrite law stuff right there. In the case of Kojima he probably viewed it as free advertising, and some other people probably do as well, but you can't just like take someone else's character and put them in your game.
I don't think this argument works well against Sonic, since Sega and Nintendo have already shown willingness to share characters for games, in the form of Mario and Sonic at the Olympic Games. I'm not saying it's definite or anything, but there's no reason they couldn't have hammered out the two deals at the same time and for about the same price.
Plus, as has been pointed out, Sonic games have sucked lately, and could Sega could probably use the ego-boost of Sonic appearing in a
good game. They're letting Bioware give it a go, after all.