The story is set in a vaguely medieval world in which a young woman has been cursed by the evil witch who has enslaved her and caused her to lose her memory. With the aid of her talking animal friends who have also been cursed (toad has a huge stone under his tongue meaning he can't feed and a crow with a gem embedded in its wing and there's a little grey kitten too who never grows up) she sets out on a journey to break the curse for herself and her friends. Along the way she meets an injured unicorn and a horny-but-moral soldier rendered impotent by a curse after refusing the disguised witch's sexual advances.
After adventures there's a 'happy ever after' for all of the heroes and the witch meets a sticky end.
In the UK the book had a deep red cover with an illustration. I read it in either the 1990's or the early 2000's. Cracking book, definitely for adults given some of the situations, language and humour.