Ok, so let's figure out this formula. First, if m is less than or equal to (n-1 choose 2) + 1, then compute the reliability of L(n-1,m-1) and multiply by p.
Once you cannot apply the first step any more, write m = (n-1 choose 2) + w. Then L(n,m) has one vertex of degree w, w of degree n-1, and n-1-w of degree n-2. Let v the vertex of degree w, A the vertices of degree n-1, and B the vertices of degree n-2. Then let R(n,m) denote the reliability of L(n,m).
In L(n,m), what is the probability that v is contained in a component with some specific a vertices of A and some specific b vertices of B? Let's compute that. All edges leaving this component must fail -- there are (a+b)(n-1-a-b) + w-a such edges. In addition, the component must itself be connected. But in L(n,m) the a vertices from A, the b from B, and the vertex v induce a subgraph that is L(a+b+1,(a+b choose 2)+a).
Ok, now we know what happens for a specific choice of a vertices of A and b vertices of B. We can choose these vertices in (w choose a) times (n-1-w choose b) different ways.
Now v must be in some component, and so if we consider all possible choices for a (i.e. a can be from 0 up to w) and all for b (i.e. from 0 up to n-w-1), we account for all possible cases. So we find that 1 = sum from a=0 to a=w (sum from b=0 to b=n-1-w ((w choose a) times (n-1-w choose b) times R(a+b+1,(a+b choose 2)+a) times [(1-p) to the power (a+b)(n-1-a-b) + w-a])).
The crucial observation is that R(n,m) is defined in terms of R(i,j) values for which i is less than n and j is less than m.
A solution in Maple for the rest. Using "option remember" makes the procedure remember the result, so that when it is called again with the same parameters it returns the result directly. This means that we do not have to store a table of results, since the procedure does so. That is enough to ensure that the result is computed in polynomial time.
Actually, one can prove the stronger claim that if i and n-1 have the same parity (i.e. are both even or both odd), then P_i >= 0 and otherwise P_i <= 0, which will imply the statement above.
We prove this by a simple induction on the number of edges, noting that P_i(G) = P_i(G-e) + P_{i-1}(G.e) - P_{i-1}(G-e) (use the standard factoring formula). Now each of these terms has the required sign by induction, so we need only settle a base case when G is a tree. But then P_{n-1} = 1 and all other terms are 0.
The basic idea is to assign every edge probability .5 so that all states are equally likely. Then choose a pair {x,y} of vertices and add an edge of probability epsilon between x and y. Using the oracle, determine the probability of connected subgraphs. You'll get something of the form (1-epsilon)*X + epsilon*Y, where (if you choose epsilon small enough) you can determine X and Y. Now X is the number of connected subgraphs (times 1 over (2 to the m)), and Y-X times (2 to the m) is the number of subgraphs with two components having x and y in different components. So, add this to a running total, and then identify x and y, so that we never count two component subgraphs with x and y in different components again. Proceed to choose another pair of vertices, and do the same; keep going until the graph is contracted down to a single vertex. Then the tally kept is the number of two component subgraphs.
It is enough to decide whether P_i is polynomial, exponential, or doubly exponential. It is easy to see from the reliability polynomial involving the N_i's that no P_i can be larger than (2 to the m) times the sum of the N_i's (consider the binomial expansion and just make every term positive). But the sum of the N_i's cannot exceed (2 to the m), so the P_i's are bounded by (2 to the (2m)), and hence are simply exponential. It is easy to see that P_{n-1} = N_{n-1}, and so a subexponential bound cannot occur as the number of spanning trees is already exponential.
Much more specific answers are possible that of course are better than the very rough one here.
Email me if you have tried to figure out what to do, but have questions that you need answered.