I am on the testnet and have my bitcoinj connected to my testnet bitcoin-qt and that is the only connection. My bitcoinj transactions aren't being relayed yet bitcoinj says everything is fine and it should be relayed.
Here is bitcoinj output
Oct 11, 2013 3:33:18 PM com.google.bitcoin.core.Wallet completeTx
INFO: Completing send tx with 1 outputs totalling 3.00 (not including fees)
Oct 11, 2013 3:33:18 PM com.google.bitcoin.core.Wallet completeTx
INFO: with 3.2999 coins change
Oct 11, 2013 3:33:18 PM com.google.bitcoin.core.Wallet completeTx
INFO: with a fee of 0.0001
Oct 11, 2013 3:33:18 PM com.google.bitcoin.core.Wallet completeTx
INFO: completed: 88073e5a03ceae663c587c5dd2c0cf9254429356d6da50a1e85ac8ca22261665: Unknown confidence level.
in [30460221010000000000000000000000000000000000000000000000000000000000000000022101000000000000000000000000000000000000000000000000000000000000000001] [02ab19d8c48d52f52e549aab88f1f178984c2a5955b43f063b4db8187937b8ddc2] / ff0dd34050e4b62be5a46d513debc8ac6489346428441f9a8d0e964be95a7d73:0
out DUP HASH160 [8c2950c9210bdd3ed73533ed90a56cb59c977a21] EQUALVERIFY CHECKSIG 3.00 BTC
out DUP HASH160 [ef54e6ec293a4df233fcea6e9125ae1a7fa7b65a] EQUALVERIFY CHECKSIG 3.2999 BTC
Oct 11, 2013 3:33:18 PM com.google.bitcoin.core.Wallet maybeCommitTx
INFO: commitTx of 88073e5a03ceae663c587c5dd2c0cf9254429356d6da50a1e85ac8ca22261665
Oct 11, 2013 3:33:18 PM com.google.bitcoin.core.Wallet updateForSpends
INFO: marked ff0dd34050e4b62be5a46d513debc8ac6489346428441f9a8d0e964be95a7d73:0 as spent
Oct 11, 2013 3:33:18 PM com.google.bitcoin.core.Wallet maybeMovePool
INFO: ff0dd34050e4b62be5a46d513debc8ac6489346428441f9a8d0e964be95a7d73 prevtx <-unspent ->spent
Oct 11, 2013 3:33:18 PM com.google.bitcoin.core.Wallet maybeCommitTx
INFO: ->pending: 88073e5a03ceae663c587c5dd2c0cf9254429356d6da50a1e85ac8ca22261665
Oct 11, 2013 3:33:18 PM com.google.bitcoin.core.PeerGroup broadcastTransaction
INFO: Waiting for 1 peers required for broadcast ...
Oct 11, 2013 3:33:18 PM com.google.bitcoin.core.PeerGroup$9 run
INFO: broadcastTransaction: Enough peers, adding 88073e5a03ceae663c587c5dd2c0cf9254429356d6da50a1e85ac8ca22261665 to the memory pool and sending to [127.0.0.1]:18333
Oct 11, 2013 3:39:44 PM com.google.bitcoin.core.AbstractBlockChain add
Here is bitcoind's debug.log when it gets the transaction
ERROR: CScriptCheck() : 88073e5a03ceae663c587c5dd2c0cf9254429356d6da50a1e85ac8ca22261665 VerifySignature failed
ERROR: CScriptCheck() : 88073e5a03ceae663c587c5dd2c0cf9254429356d6da50a1e85ac8ca22261665 VerifySignature failed
ERROR: CTxMemPool::accept() : ConnectInputs failed 88073e5a03ceae663c587c5dd2c0cf9254429356d6da50a1e85ac8ca22261665
Warning: Local node 127.0.0.1:62107 misbehaving (delta: 100)!
