Pushing a large signed transaction (testnet) using Python
Isn't it possible to switch pybitcointools to another service?

Try http://webbtc.com/api/relay The API should be similar (I haven't tested both)

It is also possible to check tx for validity (by send attempt) here: http://webbtc.com/relay_tx

(There are testnet API there, my links are for mainnet)