Are you publishing simultaneously on multiple nodes, where you have shared private keys between those nodes?
If so you should solve this by either only publishing on one node at a time, or by using different addresses to publish on the different nodes, or by manually managing "unspent transaction outputs" using the createrawtransaction command.
If not, please let us know, and we'll continue to investigate.