[Edit: I'm rewriting a lot in response to comments and clear shortcomings and errors in the earlier versions of the answer.]
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 a lot more, that $a(x)$ is indistinguishable from uniformly random according to a variety of local statistical checks.
It's important to consider a few statistical principles of random bits. First, given a finite list $L$ of random bits, all of the joint correlation information them is expressed by the biases of sums of subsets of the bits in $L$; these biases are a Hadamard transform of the joint probability distribution of the bits. In particular, of all of these sums are unbiased, then the bits in $L$ are independent and unbiased. Second, if you define the bias of a bit $b$ to be the expectation $E[(-1)^b]$, then these biases multiply when you add independent bits. Third, if $L$ is a finite list of bits and the average bias of $a+b$ for a pair of bits $a$ and $b$ in $L$ is low, then about half of the bits in $L$ are 0 and about half are $1$. If the size of $L$ goes to $\infty$ and the average bias $a+b$ goes to $0$, then in the limit $L$ almost surely has density $1/2$.
Consider first 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 $a_n$, the $x^n$ coefficient of $a(x)$ is a sum of independent biased bits. There are easily enough terms in the sum that the bias of $c_n$ converges to 0 as $n \to \infty$. Moreover, instead of one term $a_n$ you can look at the bias of $a'= a_k+a_n$ with $k,n \gg 0$. Again, the bias is low because there are contributions from many independent bits. The relevant calculation shows that $a(x)$ has density $1/2$ almost surely. A more refined calculation shows that the bits of $a(x)$ are also equidistributed modulo $n$ for any $n$, moreover that local substrings of the coefficients of $a(x)$ of a fixed length look random.
In the real problem, $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 think 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 take pairs of bits $a_n+a_k$ with $n, k \gg 0$. Assuming that $n > k$, $a_n$ contains simple terms that do not appear in $a_k$, and this is enough to give their sum a low bias. Statistics of substrings is yet another complication, but I again think that a more complicated version of the same idea should show that $a(x)$ is equidistributed, etc.
Of course the above is not a rigorous argument that a random $b(x)$ gives you a counterexample. To further support the point, I wrote a Sage program to find the distribution mod 32 of the bits of $a(x) = 1/b(x)$ out to degree $2^{20}$, taking $P[b_n = 1] = 1/\sqrt{n+1}$.
bits = 2^20; radix = 32
R.<x> = PowerSeriesRing(Integers(2))
b = R([int(random() < 1/sqrt(n+1.)) for n in xrange(bits)]) + O(x^bits)
a = list(1/b)
distrib = [0]*radix
for n in xrange(len(a)):
if a[n]: distrib[n%radix] += 1
print distrib`
Here is the output:
[16444, 16354, 16342, 16396, 16391, 16065, 16227, 16449, 16478,
16325, 16447, 16220, 16418, 16400, 16374, 16344, 16394, 16369,
16326, 16251, 16324, 16421, 16379, 16364, 16124, 16422, 16422,
16374, 16469, 16531, 16370, 16441]
If the above sketch works, it also 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 almost surely?