First, the tl;dr: this flaw is not as bad as a CBC padding oracle. It allows an attacker with continuous on-line access to a vulnerable target to conduct a slow, online dictionary attack against all previous ciphertext blocks. Given, say, a dictionary of passwords, and incurring packet I/O for each guess, you could discover whether a given ciphertext block encrypts any entry in the dictionary.
CBC is a way ("the" way, really) to take something like AES that works in 128-bit blocks and apply it across an arbitrarily long stream of data.
The naive way to do this (called "ECB") is simply to apply AES over and over in 16 byte increments. This sucks for two reasons: first, blocks can be shuffled around or replayed, because each is encrypted in isolation, and second because the same plaintext always encrypts to the same ciphertext --- so if you know the plaintext for a specific block, you can see if that block has ever occurred anywhere else.
CBC fixes that problem by XORing each plaintext with the previous ciphertext block; it "chains" all the blocks together. This neatly addresses both those problems; you can't simply look for repeating patterns because the same block encrypts to infinitely many different ciphertext blocks. Go CBC!
The one tricky thing about CBC is what you do with the first plaintext block. There's no previous ciphertext block to XOR it with. The answer is what's called an "initialization vector" (IV), which is one of the worst names in crypto. All the IV is is a fictitious zeroth ciphertext block. It's a parameter to the CBC construction; when you use a library, it'll ask for the cipher ("AES"), the key size (128 bits), the mode ("CBC"), and the IV.
Here's the thing about the IV: it's conceptually ciphertext. It's a public value. Anybody can see it. The only thing it's not supposed to be is predictable or repeatable.
The way you're supposed to do the IV is very simple: you generate 16 random bytes from your CSPRNG, use them as the IV, and then tack those 16 random bytes to the front of your message so that the recipient can strip them off and use them as the IV.
Here's what OpenBSD (and SSH2, back before 2004) did instead: each time it encrypted a message, it used the last ciphertext block as the IV for the next message.
This makes perfect conceptual sense! Think about it: what they are basically do is encrypting in one long, unending CBC stream. It's hard to see how that could even be a flaw, because a real ciphertext block seems stronger than an artificial one.
Turns out, no. Here's where that goes wrong: attacker sees a message go across the wire. Attacker has the last ciphertext block from that message. Attacker now knows the IV for the next message before the message is encrypted. Here's what can happen: if attacker can get the target to encrypt something for it†, the attacker can use for that block known-iv XOR cipherblock-prior-to-any-target-block XOR guessed-plaintext-of-target-block. The target is going to XOR the known-iv into that block (it's the IV, after all), so they cancel each other out. The block prior to the target block is going to cancel out the CBC XOR for the target block. So, what you're left with is the ECB-style encryption of the target block; if you feed iv XOR previous-cipherblock XOR "YELLOW SUBMARINE" to the target, you can tell if the target block was "YELLOW SUBMARINE", because they'll match.
The "oracle" here is the condition that the server will encypt a block of plaintext for the attacker, thus revealing the associated ciphertext. The "vulnerability" is that by pre-disclosing the IV before using it, that oracle can be used to attack any previous cipherblock.
This is a neat attack, but also a total pain in the ass to use, and certainly not an FBI backdoor in OpenBSD IPSEC.
A nit about Theo's message:
This is not a complete summary of what's been discovered about OpenBSD's IPSEC stack. Marsh Ray also discovered that sometime back in 2003, OpenBSD discovered a serious vulnerability in its IPSEC stack: they weren't verifying ESP authenticators! This was due to a straightforward bug in Angelos' original code to handle crypto accelerator hardware, and it was fixed in 2003, and that's presumably why Theo didn't mention it.
But Theo is missing the point. We're not simply interested in whether OpenBSD is vulnerable today. We want to know if there's any evidence that the IPSEC stack was ever tampered with, and particularly around the time frame that Greg Perry suggested that it was. Worse still, OpenBSD had what appeared to be†† a very serious security flaw, and they fixed it without telling users. OpenBSD users do have a right to ask the question, "hey, what gives?".
† It turns out that this is very often easy to do! For instance, the attacker might be able to invoke a web app on the target and get it to send a database query across an IPSEC link; by playing with the lengths of the input, the attacker can coerce the target into sticking a specific piece of attacker-controlled data at the beginning of an IPSEC packet. Just one example.
†† We don't know if any particular configuration of OpenBSD with or without hardware accelerators in any particular release of OpenBSD had this problem exploitably, although it sure looks like they did.