Some friends and I use this rule that says that if your hero has fatigue equal to its Stamina then it cannot perform a move action until it has at least one less fatigue tokens than its total Stamina. I've been playing with this rule that always ends up blocking our progress when playing as heroes. Is it legit?

It is not legit. At least, it's not part of the standard rules- very much a house rule.

Maybe you misinterpreted the rule that says that you cannot "convert" fatigue points in movement points (without using an action) if "fa tigue equal to its Stamina", but you are free to use a Move action :-)