Does Blockchain.info offer to set the transaction fee higher automatically when it would be advised?
When I sent a transaction from blockchain.info just some days ago, it did not set a fee at all. I had similar problems to diseone, until days later the tx suddenly was confirmed.