I have pretty consistent trouble vs characters with stealth. My Kingsguard deck is largely defensive in nature but I find it difficult to fulfill it's intended purpose when none of my characters are capable Of defending a challenge.

I'm considering just putting in a Couple The Old Palaces though they are OOH and seem somewhat undependable.

Are there any other good defenses against stealth?

You cannot use stealth against a character that has stealth himself. So find a way to give your characters, or at least your key defensive characters, stealth. The best ways will depend on what House you are playing your Kingsguard deck out of.