Allright I took fischer's provability class so I'll give it a go:

First of all whether BGP is solvable or not depends on the "powers" given to the honest vs. lying generals.  Can the honest generals "broadcast" a message to everyone else?  Can lying generals "intercept" and rewrite messages?  Do you have a mostly-synchronized clock, or even a local sense of time?  So papers basically define these "powers" and then prove a yes or no result based on them.

Let me try to couch why BGP is sometimes unsolvable in what you are familiar with: bitcoin.  Let's just say we choose one node to grab all txns and add them to the blockchain.  That node can't steal $ because it can't sign the txns.  But it could insist that there are no txns, or disappear.  If it insists there are no txns (but there are) then no progress is made (algorithm is halted).  If it disappears, can you just choose another?  No because you can't prove that it is really gone vs just slow.  That is, it could seem to disappear causing the rest of the network to pick another "issuer".  Then both nodes post a block at the exact same moment resulting in half the nodes using block A and the other half B [1].  Could you then get the network to "settle" on one of the 2 blocks?  Well, doing so is equivalent to solving the original problem (picking a block in the first place), so the above strategy made zero progress solving this problem.  

But note that if you had some relatively consistent sense of elapsed time (an additional "power"), say all nodes have time accuracy within an interval E (say 5 min), you could do something like:  the announcer has until time X to announce a block, at time X+E, we choose another announcer [2].  Ok that works but it requires a synchronized clock.  No clock is ever synchronized perfectly.  So in practice it solves 99.99% of the problem, but what happens if the announcer issues the block exactly at time X+E.  So half of the nodes will think that it is valid, the other half will reject.  So now we have to decide whether to accept the proposed block or not.  Doing so is equivalent to the original problem.  We have made no progress.

How about you use a "fitness function" to choose the best block?  Perhaps use the longest block (most txns in it).  This doesn't work because at any time someone could add a few more txns to a very old block and reissue it, wiping out the blockchain up to that point.  That is, an uncooperative node could cause the algorithm to never make progress.  Ok so let's say once the block is issued it can't be "unissued".  But what if 2 nodes "issue" conflicting blocks simultaneously.  We have to pick one.  Oops, we are back to square one!  (and what does "issued" mean anyway -- in fact it is not definable in a p2p network).

Bitcoin itself does not even solve the problem.  At any time, someone could show up with an alternate blockchain that is full of empty blocks since 2009 (say he's secretly been racing with the public chain) and all clients would switch to that chain where no transactions have happened.  So in fact from a theoretical perspective the algorithm can be proved to never make progress.  However, from a practical perspective this is unlikely to happen, and if it did, I as a community we could throw in some kind of hard coded change (essentially a centralized decision hard-coded in a new client) that forces "our" chain to be chosen.  

So what's cool about Bitcoin is if it breaks down it can essentially "devolve" into (worst case) a centralized scheme.  No worse then we had before Bitcoin (and actually a whole lot better in other metrics).


[1] http://cs-www.cs.yale.edu/homes/arvind/cs425/doc/fischer.pdf
[2] http://research.microsoft.com/en-us/um/people/lamport/pubs/reaching.pdf