My memory is not that reliable but here goes.
For the green-haired martial artist (forgot the name):
Go to an island with a village surrounded by trees (warrior's village??). Talk to every villager for clues especially the Leader's guard. Then, I think there would be an option to challenge everyone to a fight. So, spar with every villagers including the chicken. After finishing all the fight go to the guard and he will let you in. Go talk to the Warrior Leader and fight him. After winning, You will get a cg scene and I think a heart power-up. Go outside and you will see the green haired guy. Talk to him and he will challenge you for a fight. If you beat him, there would be an option to recruit him. After gaining the martial artist, you can now enter his house surrounded by tress near the castle (the locked house before).