Messaging contacts color change
I see a discussion in AndroidForums stating that this behavior is a strange bug.  It seems that few experienced this issue for whom the color changed after receiving an emergency message.  They also say that deleting such messages restores the color. If you had received any such emergency message, can you please try to delete it?

Out of curiosity and the attraction of bounty led me to search for this issue else where. I do not have an S3 or know anyone having S3 to confirm this.