I don't see why the tribal costume can't be added there was no problem adding ZSS alt costume or Shulk's definitive costume I can see them doing some changes though like adding a short some bandages or something.
There is a difference, although it is a silly one. You see in Japan it is different for a character to have only a swimsuit bikini, than having only panties and a bra, even though they are both quite the same thing.
This is the reason why many fighting games have swimsuit costumes for some characters, because it somehow isn't as bad/the same as having a character in their underwear.
It is silly, yes, but that's how the rating works around there (probably even outside of japan too, but I'm not completely sure). It's almost as funny to me as the "no guns policy" in age ratings. You can't have a pistol that shoots bullets, no, but you can have a RPG that fires a freaking explosives that would cause a whole lot more damage in real life than a bullet. It's really one of the silliest things to me. I mean, I know having explosives in real life is kinda more less likely than having a gun, so I guess the age rating boards think explosives are okay because no kid could get their hands on them (I dunno) and because explosives can be "cartoony" or something. But still, it's just really silly to me.
The only way I'd see her tribal costume working is that they would give her a big skirt (with a blackhole like peach has
), instead of the loincloth, and her top part would be more "shirt like" that would cover more. Because if you read this
http://www.sourcegaming.info/2015/09/18/cero-and-palutenas-censorship/ article and compared the pictures that it has, it really shows how strict they can be in japan with this stuff.
Palutenas skirt (or what ever it's called, a dress? I'll go with that) goes lot more higher from the side in the western model than in japans, because they deemed it too "sexual" looking for the age rating they were going for. Meaning that Krystals loincloth would never go through with the current age rating there, unless they would somehow see it like "oh this is an anthropomorphic animal with tribal clothes. Yeah this clothing is okay, no need to change anything, because it isn't a human after all ( ͡° ͜ʖ ͡°), move along"
I doubt even bandages would necessarily fix her clothing issues, since the rating board could deem the bandages as "not really clothing".
The problem isn't that Nintendo or Sakurai would care for this stuff, it's simply the oddly strict age rating board (cero) that is the issue. And if they say it isn't okay, then you have to do it differently until it is deemed as okay, if you want the lower age rating.
Shulks secondary costume is okay, because it is a swimsuit, and cero thinks it's okay to have 'em. People are at the beach in them but nobody is anywhere in public in their underwear (or they are but most likely they'll get a ticket for doing so). And the jogging/training (I don't know what it's called, leave me alone :< ) clothing of Samus isn't a bikini nor an underwear, it's "actual clothing" so it's fine for cero.