I don't see the problem with beheading the deserter. If you desert from the Night's Watch you don't get a trial, correct? The walkers have been gone for a thousand years (or some huge amount of time), he told Ned what he saw and Ned blew him off. I guess he could have sent a scouting party to try and find the remains, but I don't blame Ned for that. If we didn't see the prologue and the walkers, I doubt we'd believe him either.
It's a problem in the sense that it's a example of of Ned's weaknesses: concepts of law and honour overruling logic and critical thinking. This is where characters like Tyrion and even Bran come into play, showing that in a world of magic and peasants and scheming there's still room for an intellectual approach to situations.
Ned's character flaw is that he is, to a large extent, a simpleton. He is bound to culture, tradition, rules, laws, and honour, and has a very,
very difficult time stopping and allowing himself to critical think without the weight of the past holding him back. As Bran says to him at the beheading "So he's a liar". The answer to this is "We don't know, but we killed him anyway". Robb and Ned try to dress it up as honour, something at ~must be done~, but Bran stops to question why something ~must be done~ at all.
Ned fucked up his plan at King's Landing the exact same way. He wanted to honour Robert, and he wanted to honour law as he saw it in just and true politics. He ignored the logical advice of people who knew the situation better than he did, those who knew full well "honour" was a crock of shit, and unsurprisingly the whole thing blew up in his face.
People like Tyrion and co are there to question the rules that should be questioned.
I think Robb's problem was that he tried to flip-flop between being honorable like his father and doing what he needed to win. If he was honorable like his father, he would have sucked it up and married Walder's daughter (and prevented his problems from occurring). If he was playing to win he could have dealt with the Karstarks besides killing the leader. He tried to have it both ways and that's what really got him.
I agree. Robb wanted to be young and impulsive and also live up to his father's honour, and his juvenile approach to the whole thing wound up having him, his family, and his army murdered. But that's the point. Like Ned being bound to honour and law, Robb saw fit that Karstark had to lose his head because rules. This was a bad military and political decision. It was not a good idea. It was against the advice of everyone. But he did it anyway, because honour.
Game of Thrones underlying message is that honour, rules, and traditions are all a crock of shit in the grand scheme of things. Like history, ruthless people will see your adherence to silly concepts and use them to fuck you over and over again.