I did not encounter this problem,quite the contrary, it is way too easy to have good relations with everyone in your faction, since you always gain more positive relation than negative in the votes. The fact that you are considered friends by just reaching a measly +15 relation is also quite silly and makes it way too easy to get the support by other nobles for pretty much anything.
The same is true for all ways to earn relations. Quests that give you relation hit, always grant more relation bonus than penalty, So there is a clear upward spiral over time and only if you actively go out of your way to **** with people could you ever go into the negatives.
Execution is a very fast way to make everyone hate yo though, but ofc this is always contained to a faction/culture, so if noone is left alive of said faction/culture, who really cares at the end....