Created a new directory in all Managed Nodes, where permission is 777. But yet can't be used as storage path for backup.

So it dosent have to be local or NAS. Ours was a mounted drive, that was on a SAN, so it in essence was NAS but it was also local. We always had a yellow warning in the CMC for the back up, but the backup worked without an issue. We had issues with updating where a host was changing permission levels. I had concluded that it was a security application that was reverting the permissions because I could manually change them, update the cluster and it would work. But weeks later when the auto update would kick off, it would fail due to permissions and I would have to change the permissions again on that one failed node. it was odd.

I feel that you issue is very similar if not the same, just at a backup permission level.