Happened to me the first time I made payment via Priceline's own online payment system (~$5k).
They gave me the run around but it was made available about 5-7 days later.
Have been using Chase Billpay since then and it hasn't happened since.
I think financial institutions consider the source when making funds available for new(ish) card holders.
Chases billpay system is setup in a way that the payment is funded (immediately taken from your account) when you setup the billpay.
If the $$ isn't there they billpay isn't processed. I think processes like these (and the reputation/size of the sending bank) makes the difference on the receiving end and how they treat your payment. Not saying its the only things that matters but it helps.