I did the catman alaiance twice, and marandia's dice once. I was still indiffrent with them and I still could not get the quest, saying something to the affect that "Though you haven't made us mad, you haven't done squat for us either".
I have a 54 shammy with some skill in alchmy. I took some Edudite meat that I have in the bank and made some Essence of Erudin. Suddenly my dwarf paladin that is ally with the DW Knights and all 3 of the casters guilds and I think ally to the guards, suddenly he is amiable to them....
I had no problems getting her to go out and slay those kobold shammys, the guy outside told me to go smack down the poachers....no problem what so ever getitng the quest.
hope this helps!!