The offensive content problem may even have something to do with the appearance of their "monster" character being confusingly similar to typical portrayals of the devil (red character with horns), which itself is can be an offensive image in many cultures regardless of context. That's why feedback is so important in these review processes, especially with something so subjective.
As an aside, the devil thing isn't isolated to non-Western countries either. Linda Branagan famously recalls one instance of where the BSD "Daemon" mascot, which also looks devil-like, nearly got her into real trouble in Texas: http://rmitz.org/freebsd.daemon.html
Reading this story, its interesting how similar Texas and some places in middle east can be. Dust, deserts, oil, lots of guns, and... fanatics (to avoid calling them fundamentalists).
Malaysian here. We do have a large, extremely devout conservative demographic here, so I can see why Microsoft would choose to be on the safe side. Plenty of foreign artistes were banned from holding concerts here due to perceived lack of morals.
On the other hand, our newspapers regularly publish raunchier content without much fanfare.
In Malaysia's case, it's more because of the way race and by association religion is split almost 50-50 among the local population.
The result is that Malaysia has a large enough non-Muslim population to avoid becoming a full-blown theocracy like Saudi Arabia, but still have a large enough religious base to be considered a 'conservative' country.
As an aside, the devil thing isn't isolated to non-Western countries either. Linda Branagan famously recalls one instance of where the BSD "Daemon" mascot, which also looks devil-like, nearly got her into real trouble in Texas: http://rmitz.org/freebsd.daemon.html