The recipe looks fully doable with ale yeast. You won't get exactly the same beer that Surly intends, but unless you're going for a perfect clone there's no reason that should concern you.
For a smoke beer, I'd personally want something clean and malt forward, and I'd definitely avoid anything phenolic. If you can get anything you want, consider using an altbier yeast like WLP036. Otherwise, any clean ale yeast (like WLP001/Wy1056) should work fine.