Receiving `error: {"code":-25,"message":""}` on sendrawtransaction with v0.9.3
After connecting to bitcoin-core (0.10.0rc3) I received:

ERROR: CScriptCheck() : 620186f101b7db97393af8747923db4cf3f30c3c3c48f4c7cfc23567b6d9ca07:0 VerifySignature failed: Data push larger than necessary
ERROR: AcceptToMemoryPool: : ConnectInputs failed 620186f101b7db97393af8747923db4cf3f30c3c3c48f4c7cfc23567b6d9ca07


(Thanks bitcoin devs for adding sane error messages!)

From here I noticed I was building the transaction with an outdated fork of bitcoin-ruby, updating to the latest bitcoin-ruby fixed this issue (On both 0.9.03 and 0.10.0). Still not sure why it would only relay after a bitcoind restart, will edit this answer if I figure this out.