What is the best way to recover from an accidental double-spend?
Apparently to get the RPC command removeprivkey you'll need a build of the Bitcoin client which includes pull #220 (which has been merged into main).  The latest version (currently v0.12.1) contains this feature.

Here are the instructions to do that:

Step 1. Back up your wallet.  You are performing wallet surgery here, ... and doing things you might not have intended.

Run Bitcoin as a server, e.g.,


  $ ./bitcoin-qt -server


Then 

If you've encrypted your wallet you'll need to open it for RPC


  $ ./bitcoind walletpassphrase [passphrase] 1000


Then


  $ ./bitcoind dumpprivkey [bitcoin address]


Then copy and paste the private key it provides.
Then


  $ ./bitcoind removeprivkey [bitcoin private key]


Then close bitcoin-qt.

After that


  $ ./bitcoind -rescan