I think they should pick their traits more according to who they are, and NOT randomly pick them. Maybe 3 predefined and one random.
That's one option, but personally I think the better way to go would be to WEIGH the traits differently, specifically having the AI's inherent trait carry more weight than any of the other ones they pick-up. This, along with affinity and proximity should be far more important to whether or not the AI likes you than the secondary traits the AI picks up. Wouldn't fix all the issues, but would be a step in the right direction.