We'd booked the actor long, long in advance. At the last minute, he bailed to do a DS9 episode playing, essentially, the same character, despite our having first dibs.
So I killed off the character. Didn't change the story by the smallest measure. May actually have helped, since it raised the stakes in the story right from the start.