Mine finally went through and confirmed. The network is very congested right now and you have to pay slightly higher fees to get things confirmed in a reasonable time. Since your transaction is already on the network, it will sit there until a miner picks it up. It will not get returned to the sender or anything like that.

This is a good site that estimates how many blocks before a confirmation based on current network congestion and fees per byte.

Here's another cool chart that shows the size of the mempool. Mempool is basically all transactions on the network that are waiting to be mined into a block. Notice how just in the last few days it's gone from about 5-7 MB all the way up to 42 MB. Remember...max block size is 1 MB. So even if everyone stopped spending bitcoins right now, it would take over 40 blocks to clear out all the transactions that are waiting. Miners will leave low-fee transactions sit and include transactions with fees.

I didn't know any of this until I started asking around about my own stuck transaction (which is now unstuck).

Also, to be clear, even though it was a hassle to get my BTC back, Predictious has fulfilled their obligations to me at this point.