I think that your conjecture is not true and I can outline a reason.

As in your paper, let's express the sequences as binary power series $a(x)$ and $b(x)$, so that their relationship is the equation $a(x)b(x) = 1$.  (I am just changing your variable from $q$ to $x$.)  My conjecture is that if you choose $b(x)$ at random with slowly decreasing density, then with probability 1, the reciprocal $a(x)$ is uniformly distributed in every congruence class modulo every $n$.  In fact, I conjecture the stronger property that for every fixed polynomial (not power series) $p(x)$, $a(x)p(x)$ has density $1/2$.  (At least I think that that's a stronger property.  Anyway I conjecture both properties.)

As a warmup, let's consider a toy model in which $b(x)$ is random as in the previous paragraph, and $a(x) = b(x)c(x)$, where $c(x)$ is some specific power series such as
$$c(x) = 1+x+x^4+x^9+\cdots.$$
Let's suppose that the $x^n$ coefficient of $b(x)$ is 1 with probability $1/\ln (n+3)$ (say).  Then $c_n$, the $x^n$ coefficient of $c(x)$ is a sum of independent biased random variables in $\mathbb{Z}/2$, and when you add these variables, their biases multiply.  (This point is clearer if you let $C_n = (-1)^{c_n}$.  Then $C_n$ is a product of independent random variables whose expectations multiply.)  There are easily enough terms in the sum that the bias of $c_n$ converges to 0 as $n \to \infty$.  The same is still true if you replace $c(x)$ by $c(x)p(x)$ for any polynomial $p(x)$.

Now in our case $a(x)$ is given by the functional equation
$$a(x) = b(x)a(x^2).$$
This is more complicated, but $a(x^2)$ can still play the role of $c(x)$.  In particular, we can say that the $x^n$ coefficient of $b(x)a(x^2)$ is a sum of simple and compound terms, where by definition the simple terms use $b_k$ with $k > n/2$.  These random variables do not influence $a(x^2)$.  What I expect happens is that the sum of the simple terms is a bit with very low bias, and the bias cannot be boosted by adding any hypothetical combination of compound terms.  And, as in the toy model, you can equally well look at $b(x)a(x^2)p(x)$ for a polynomial $p(x)$.

In fact, even though it is more complicated, it could be more favorable.  In the toy model, if you thicken $c(x)$, you can correspondingly thin $b(x)$.  In the real problem, the density of $a(x^2)$ comes from the density of $a(x)$, which then further dampens the bias of later coefficients of $a(x)$.

----------

If the above sketch works, then it motivates this question:  Suppose that a number $0 \le x \le 1$ is chosen at random with independent but biased digits in base $b$.  For concreteness suppose that the digits are all $0$ or $1$ and that the density goes to 0 sufficiently slowly.  Then is $1/x$ at [$b$-normal number][1] almost surely?


  [1]: http://en.wikipedia.org/wiki/Normal_number