Solution:

Working from the outside in, $\log_2(\cdot) = 0$ forces $\log_{2^a}(\log_{2^b}(2^{1000})) = 1,$ so $\log_{2^b}(2^{1000}) = 2^a,$ so $2^{1000} = (2^b)^{2^a} = 2^{b \cdot 2^a}.$ Hence $$b \cdot 2^a = 1000 = 2^3 \cdot 125.$$

Since $a \ge 1$ and $b$ is a positive integer, $2^a$ must be one of $2,$ $4,$ $8,$ giving $(a, b) = (1, 500),$ $(2, 250),$ $(3, 125).$ The sum of all possible values of $a + b$ is $501 + 252 + 128 = 881.$