Samsung S3 4.3 update - Cannot change notification sound?
Thanks to @Shywim's comment, I checked the settings of the Messaging app. Indeed it's got a custom notification sound settings. (You can adjust the settings only if your phone is not muted.)