Time complexity of a problem in probabilistic inference on a Bayesian network
Your problem is equivalent to:

Given: real numbers $a_1,\dots,a_n \in \mathbb{R}$; a real number $t \in \mathbb{R}$
Goal: count the number of binary vectors $(x_1,\dots,x_n) \in \{0,1\}^n$ such that $\sum_i a_i x_i \ge t$.

I think this problem is #P-complete, so you shouldn't expect any polynomial-time algorithm for computing it exactly.

Let me explain why.
Let $\ell(x,y)$ denote the likelihood of the states $x,y$, $\ell(x) = \ell(x,1^n)$, and $L(x) = \log \ell(x)$ its log-likelihood.  Then $L(x)$ has the form

$$L(x) = -n \log 2 + \sum_i \log p_{i,x_i}.$$

An assignment $x,1^n$ satisfies $E$ iff $L(x) \ge \log \epsilon$.  Note that

$$\log p_{i,x_i} = \log p_{i,0} + x_i (\log p_{i,1} - \log p_{i,0}).$$

Letting $a_i = \log p_{i,1} - \log p_{i,0}$, we have

$$\sum_i \log p_{i,x_i} = \sum_i \log p_{i,0} + \sum_i a_i x_i.$$

If we now let $t = \log \epsilon + n \log 2 - \sum_i \log p_{i,0}$, we find that $x$ satisfies $E$ iff $\sum_i a_i x_i \ge t$.  So, given $t$, we want to compute the probability that a random chosen $x$ satisfies $\sum_i a_i x_i \ge t$.  This is equivalent to counting the number of $x$'s that satisfy $\sum_i a_i x_i \ge t$.

According to https://cstheory.stackexchange.com/q/19758/5038, this problem is #P-complete, so you shouldn't expect to find any polynomial time algorithm to compute the answer exactly.

However, there are techniques for approximating it: for instance, you could use algorithms for estimating the number of lattice points in a convex polytope (see, e.g., https://www.math.ucdavis.edu/~deloera/RECENT_WORK/semesterberichte.pdf) or computing them exactly in super-polynomial time (https://cstheory.stackexchange.com/q/22280/5038, https://cstheory.stackexchange.com/a/6464/5038).