So ... they're recognized because of ... magic?They don't have to recognize that person as a specific folk hero; they need to recognize that they seem like a hero. There's no magic and no turning brains off; just a bit of creativity.
Did the PCs just arrive there minutes ago? OK, you might have a problem. Have they been there a day or longer? No problem at all. If they fought a monster, then while they were in the middle of battle some NPC woodcutter heard the sounds, saw what was going on, and then ran away because they don't want to be near a battle--but they saw the PCs. Or maybe they found the monster's corpse and then saw the PCs, spattered in blood, and put 2 and 2 together. If the PCs sat around a table at the pub talking about their plans, someone overheard them and came to the conclusion the folk hero was the leader of the party. If the PCs decided to sell some gear that they looted off of bodies they killed, word is going to get around.
Then, because the folk hero has that trait, they latch onto them as the hero they deserve.
Or maybe the PCs inadvertently did something that helped the townsfolk--remember the Firefly episode "Jaynestown"? Or maybe the PCs didn't do anything, but arrived right after something particularly fortuitous happened, and the NPCs haven't learned that post hoc doesn't necessarily mean proptor hoc.
Because when you get down to it, it is, as Oofta said, a very minor benefit--the NPC is willing to give the PC a nice bowl of hot soup and let them camp out in the barn. It seems weird to not let this happen because the PCs are new in town.

I was thinking about this a bit more and the biggest issue I have is how they describe the feature "Since you come from the ranks of the common folk, you fit in among them with ease." Which ... okay. But most other backgrounds could have a similar origin story. Heck, even the noble raised by commoners is a common trope in fantasy. Why is the folk hero really any different? If the entire party just saved the village from an invasion by bloodthirsty trolls, why would the folk hero get any special recognition?
It's just, I don't know, weak. There's not really much there there so to speak. I'd rather chat with my players and find out if they care much about this kind of stuff and if they want a tie into potential campaign plot hooks. Which is why I think the new backgrounds are better, they give actual concrete benefits without having to just say it works "just because".