The allegiance system is (by design) very open ended, I susupect your players are lost in too many options. Remember that an allegiance can be almost anything. Try talking with them and figguring out what is important in their character's lives (maybe someone wants to be wealthy, or is a patriot of their kingdom, maybe another person hates Nordenhimer's with a passion or is in love with an NPC) then try and make those character goals into "allegiances".
Hope that helps.