outbound, and no tx in the blockchain. It is a 0-conf tx
Ok, if the transaction has no other problems then leave bitcoind running and it will rebroadcast the transaction after some time (e..g, half hour).
If there is any chance the transaction is a double spend, it not only won't confirm, there's no easy way to remove it. Was a copy of the wallet.dat used elsewhere, or were there addresses imported where a double spend might have occurred?
So, first give the client a chance to rebroadcast if that's not been running for a half hour. I don't know the next step though --- perhaps a pastebin from the last few dozen lines of debug.log?