Does convolution done via the FFT _undo_ computational gains when signal has zeros every other sample? Suppose we have filter $h[n]$, length $N$. If I use it to do convolution in the time domain, then there will be $N$ multiplications each time during the sliding. (Ignore border conditions for now). However if say $h[n]$ had zeros every other sample, then there would be half that number of multiplications, so ostensibly I save in computational load, since I have half the number of multiplies to do. 

So then in conclusion the speed of convolution in the time domain is related to the number of zeros. 

Now suppose I did this convolution via the multiplication in the frequency domain using the FFT instead. It seems that I would undo any gains I could have had, zeros or no zeros, because when we do it via the FFT method, it is agnostic to the actual values of the samples of the signal and filter.

Is this a correct assessment? If so, might there then be cases where a good old fashioned convolution in the time domain is in fact much faster than an FFT?
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.