Does convolution done via the FFT _undo_ computational gains when signal has zeros every other sample?
If you know ahead of time that your filter pulse response has zeroes in alternation, then you can use a different FFT routine to speed up the convolution. On the other hand, if you simply pass the filter input and the pulse response to a generic computational subroutine that will spit out the filter output given $x[n]$ and $h[n]$, then yes, the zeroes will be handled no differently than any other inputs and will not save any computation at all.

Example:
Suppose that the (FIR) filter pulse response is $\mathbf h = 1 \quad 0 \quad 1 \quad 0 \quad 1$.  Then, the filter output is

$$y[n] = x[n] + x[n-2] + x[n-4]$$

and so the filter output is alternately
the sum of three successive even-numbered inputs and 
the sum of three successive odd-numbered inputs.  So, knowing that
$\mathbf h$ has alternate zeroes, we could proceed as follows.


Create a filter $\hat{\mathbf h}$ by decimating $\mathbf h$ 
(or downsampling) by a factor of $2$. Thus, $\hat{\mathbf h} = 1 \quad 1 \quad 1$ in the example.
Decimate $\mathbf x$ to create two input streams 
$$\mathbf x_e = x[0]\quad x[2]\quad x[4] \quad \cdots ~~\text{and}~~
x_o = x[1]\quad x[3]\quad x[5] \quad \cdots$$
Apply $\hat{\mathbf h}$ to the two streams to get $\mathbf y_e$ and $\mathbf y_o$.
Recombine $\mathbf y_e$ and $\mathbf y_o$ to get $\mathbf y$.


If FFTs are used anywhere in doing the needed convolutions, note that the
FFT of $\hat{\mathbf h}$ needs to be computed only once, and various tricks
such as overlap-and-add etc will have to be applied separately to the two
data streams. Note also that the FFTs can be shorter (though we have to
do two of them), and a crude comparison
says that 
$$2\left[\frac{N}{2}\log_2\left(\frac{N}{2}\right)\right] = N\log_2\left(\frac{N}{2}\right) &lt; N\log_2 N.$$
More exact comparisons with actual numbers may reveal a different tradeoff.