This appears to be the root of the problem.  My client has this transaction:
39445bebc8b69dbfb020d437dd3738a8fc66681b507a75363729919ef47c3e02

Here is the output of getrawtransaction:
0100000001edc13c11e603787b66d764d518483852d31ff5ad40a92fef9e3f94e830c3e5c501000 0006c493046022100ffe7d367ae2cff45db200b1377ab023d3eaa989e21f7c9bd8791c11222799b 35022100bb906cbe08559d46c44f4f8ccea094787f37d0479b49fe7331d417de214f3df60121020 c12d127683f84315d701832383a41fc063502cc50fd4d8b56c68176df1903b4ffffffff02723346 00000000001976a914b69925f93434c2fa296c7f2e994df5b0c2bfd56488ac580f0200000000001 976a914e1acf118a792ad15264b6e4543d66afbc9372c7b88ac00000000

On decode, it shows this:
 "lock_time":0,
   "inputs":[
      {
         "prev_out":{
            "index":1,
            "hash":"c5e5c330e8943f9eef2fa940adf51fd352384818d564d7667b7803e6113cc1ed"
         },
         "script":"493046022100ffe7d367ae2cff45db200b1377ab023d3eaa989e21f7c9bd8791c11222799b35022 100bb906cbe08559d46c44f4f8ccea094787f37d0479b49fe7331d417de214f3df60121020c12d1 27683f84315d701832383a41fc063502cc50fd4d8b56c68176df1903b4"
      }
   ],
   "vout_sz":2,
   "hash":"39445bebc8b69dbfb020d437dd3738a8fc66681b507a75363729919ef47c3e02",
   "vin_sz":1,
   "out":[
      {
         "address":"1HeVSr4fY9vHsNYQW54Ln6dvqBdACtrZzg",
         "script_string":"OP_DUP OP_HASH160 b69925f93434c2fa296c7f2e994df5b0c2bfd564 OP_EQUALVERIFY OP_CHECKSIG",
         "value":4600690,
         "script":"76a914b69925f93434c2fa296c7f2e994df5b0c2bfd56488ac"
      },
      {
         "address":"1MaGDNKRsbaTFPZ37xEVrxW722ZnHFyhwX",
         "script_string":"OP_DUP OP_HASH160 e1acf118a792ad15264b6e4543d66afbc9372c7b OP_EQUALVERIFY OP_CHECKSIG",
         "value":135000,
         "script":"76a914e1acf118a792ad15264b6e4543d66afbc9372c7b88ac"
      }
   ],
   "size":227,
   "version":1


When I try to push it to the network, I get:
An outpoint is already spent in [DBBitcoinTx [txIndex=47534292,  getEstimatedBTCSent()=0, isGeneratedBlockReward()=false, getTotalBTCSent()=0, getHash()=518fc4bf6cfbe142c29fd54f2d623807ce02c19d88c48d0185bc16f8e14fa41a, getVersion()=1, getSize()=231, toString()=BitcoinTx{hash=518fc4bf6cfbe142c29fd54f2d623807ce02c19d88c48d0185bc16f8e14fa41a, version=1, lockTime=0, in=[], out=[]}, getClass()=class piuk.blockchain_db.DBBitcoinTx]] [(47477784, 1)]

How can an output already be spent if the transactionId doesn't show up on the blockchain?