The exact permission in the code is something like this:
Allowed to rename = IsAdmin || ScopedModeratePermission || (IsDiscussionAuthor && CanReply && RenameTimeSetting)
So for regular users who aren't moderators, it's the last 3 elements that need to be true at the same time. The time setting must be indefinitely or within time, they need to have authored the discussion, and they need to be able to reply to the discussion.
