Protection question

[Akarian]

I had a creature out, Nemesis of reason. My brother put a Pillary of the sleepless on it, what it does is of no importance. It's a black enchantment though. A couple turns later I played Akromas memorial, which gives all creatures I control protection from black, would Pillary go to the graveyard when akromas memorial comes into play?

[klicker]

the enchantment would fall off and go to graveyard

[mtg8433]

What if instead of gaining the protection, that creature would gain shroud.

Would the enchantment still fall off?