I think the main character is a king or a great fighter and has a woman with him. I can't remember how she is related. They are out in a wasteland, and a man comes up to the party and ends up poisoning the king by offered him something to drink. He does this to blackmail the king to obtain help. There is an antidote but in 3 doses in 3 different places. There is also a wizard of some sort with his wife that is protecting a castle with magic traps, but some how the traps don't keep something out. There is also some kind of a statue (of a king?) at the exit of the wasteland. Does this tell anyone enough info that can help me find this book to read again?