In all cases we get the next trouble in simplewallet:
make sure you run monero-wallet-cli, not simplewallet, it's been renamed, so if you run simplewallet you're probably running an old version.
Error: transaction <9e2e37247a520f170198ea827ba000eb93460eb481f3a136e69dd05b503985c5> was rejected by daemon with status: Failed
[wallet 49UHzL]: 
Message in bitmonerod:
2016-Oct-10 18:50:51.028434 [RPC0][on_send_raw_tx]: tx verification failed
make sure you run monerod, not bitmonerod, it's been renamed, so if you run bitmonerod you're probably running an old version.
If this persists, then in monerod:
set_log 1
And try again. You will get more information about why the daemon is rejecting the tx.
It could be a double spend, there were a couple bugs which would cause the wallet to get confused about what's spent. If so, run "rescan_spent" in the wallet.