Get your honor up... (Release captured lords) And you'll suddenly find yourself friends with people you've never even met before...
I abandoned my first game in Warband because I screwed up a fair things but I had like 50 Honor and when I ran off to join help that Arryn the Prom Queen or whatever she's called help secure her place on the throne of sassanid empire some of the lords I was fighting had like 40+ relations with me.
Also if you want fiefs, DO NOT BECOME THE MARSHAL. >_> Your Controversy skyrockets because you get blamed for everything, even on a peasant stubbing his toe on a rock.