How many nodes are you connected to with your sending client?  Blockchain.info is very easy to get broadcast to because they have 2500+ connections with their custom implementation.  You need more connections to increase your chances to get to miners maybe?