I've gotten the same message a couple times recently. Assuming it's the same cause here's what seems to be happening, at least in my case:
1. You went stingy with the transaction fee. So the TX goes to the nodes and sits in the mempool, but the miners are prioritizing other TX over it. It sits unconfirmed a couple days.
2. Eventually Blockchain drops it and gives you that message.
3. But your wallet keeps pushing the TX and it is still in a mempool somewhere. The wallet keeps treating it as spent at this point.
4. Eventually it does get confirmed, and shows up again on Blockchain. This is the point you need to get to. :-)
I'm not familiar with Payza, but you can look into whether they have Replace by Fee or whatever it is called, or the Child pays for Parent capability to push through the TX. You can also try the Via BTC accelerator if the TX was high enough for their service. That's saved me a couple times. Otherwise, I'd say wait and see if it confirms over the weekend.
