I've encountered this same bug.

Also, henchman don't actually cost gold. You just need the amount of gold in your inventory to hire them.