"Is "Chaum's design" the one where merchants are assigned identities, payment is offline but specific to the merchant's identity, and a double spender's identity is revealed if a coin has been spent at two different merchants?"
More or less; the important concept is that a double-spending attack will not only be detected, but that it will both reveal the identity of the attacker and allow the attacker to be blacklisted. It is not necessary to differentiate "merchants" and "spenders;" re-spending a transferred coin in an offline protocol is possible (without sacrificing the "double-spending reveals the attacker's identity" property).
"Bitcoin provides a property none of those other systems provided - freedom from a trusted "issuer"/bank/etc"
Bitcoin may do this, but it does so by sacrificing rigorous security and offline payments. Even if we assume that a monetary system without any authorities makes sense (I am doubtful about that), a system where the attacker's effort is linear in the system's parameters is not a system that can be trusted with any significant amount of money.
"What I meant to say is that being built from those primitives, it could be proved as secure as those primitives"
Except that Bitcoin is not a signature system, nor is it a hash function. The only statement that can really be made is this, "Bitcoin's security is dependent on the use of a secure signature system and a secure hash function." Again, look at the email robustness example; a system built from secure cryptographic primitives can still fail to meet its security goal.
"When we give up trusted authorities (and specific "parties" necessarily created by some trusted authority), what remains? What differentiates "the majority" ? One of the few things I see is computing power."
Parties are not created by authorities; parties are what communicate in a distributed system. In the commonly used model, the attacker is allowed to control some number of parties and coordinate their actions; any party, honest or malicious, can scale their computation by some polynomial of the system parameters.
In the case of Bitcoin, parties can enter or leave the computation at any time, without having to send messages to the other parties. That introduces an entirely different challenge, since the attacker can keep adding parties to the system, eventually controlling a majority of whatever capability the parties have. That is not to say that some notion of security cannot be achieved; rather, it means that any notion of security based on a "majority" of anything cannot be achieved without some way to restrict the number of parties the adversary can enter in the system.
The anonymous remailer system faces a similar problem: an attacker can create as many remailers as he wants. In the case of anonymous remailers, however, it is OK for the attacker to control a majority of parties, since it only takes one honest remailer for the system to be secure (i.e. for messages to be anonymized). That should be the goal of Bitcoin: the ability to prevent forgery and double spending as long as some honest parties remain in the system (assuming such a thing is even possible without a central authority; it could be the case that no such protocol can exist).
"Sybil attacks have been defined away, as they depend on some notion of "parties"."
I think the parties in Bitcoin are the people who use it. After all, the point of Bitcoin is to facilitate monetary transactions between its users.
"The "honest parties" wishful-thinking has vanished, leaving only "majority of computation" as the network authority"
No, there is still an issue of "honest parties" versus "malicious parties." Honest parties in Bitcoin are people who are willing to follow the rules and who are not trying to double spend their money or spend money they did not mine/receive. Malicious parties are those who are trying to break the rules by whatever means are available to them. The fact that the majority of computational resources is what decides the validity of the transactions just means that a malicious party needs to collect the majority of computational resources; this is not infeasible, and it is only somewhat impractical (and only really impractical for individual people).
"Of course the merits of this security model are still up for debate, but it seems to mostly work."
It seems to mostly work because nobody with the resources needed to carry out the known attacks cares enough about Bitcoin to do so. The NSA is too busy spying on people to worry about Bitcoin, and companies with large numbers of computers like Amazon or Google are busy using those computers to run their businesses.
This does bring up an interesting point, however: an attacker would only really need such large computing resources during the duration of the attack. The hardware would still be useful after the attack, and the attacker might simply sell it or use it for some profitable purpose. I think the only thing that really prevents fraudsters from doing this is the lack of capital/credit needed to procure the equipment in the first place (let's put it this way: if you were running a bank, would you give a billion dollar loan to someone whose business plan was "defrauding Bitcoin users?").
"Erm, given that the fork was a rare event, it actually shows that Bitcoin is mostly solving the problem, just not perfectly."
The problem is that the fork was caused by parties failing to adhere to the protocol. If Bitcoin is not resilient to parties failing to follow the protocol due to a bug, then it is also not resilient to parties that do not follow the protocol because of a coordinated attack. In other words, Bitcoin is not secure against malicious parties (which are defined as parties that do not faithfully follow the protocol).