So that's the reason my transaction was stuck almost for 24 hours, the exchanger canceled the order and I started to panic (a little). Luckily it eventually confirmed and we were able to sort things out with the merchant. Oh and I did pay the recommended fee that Blockchain.info automatically adds to the transactions!