There are black and white souls. A black soul gem only accepts black. A regular soul gem only accepts white.
This is probably the problem you are having.
I don't think anyone's given a completely full explanation here, so expanding on what Tale said:
Non-sentient creatures have WHITE souls. Their souls can be bound in the regular sorts of soul gems you mostly come across.
Men, mers, and other sentient creatures have BLACK souls. Their souls can only be bound in a BLACK soul gem, or equivalent.
I haven't heard of either of these artifacts, but I would guess that with Azura's Star, you can only bind WHITE souls, but with the Black Star you can bind BLACK souls.
Oh btw, I learned all this in a book I came across called something along the lines of "Souls: Black and White," within the game
