That transaction is 3291 bytes in size and the fee is 55673 satoshi. This means you're only paying 16.9 satoshi per byte (0.00017 per KB). It's not high enough.
Thanks for clarifying that. I did increase the txin fees a few days back to the recommended values, not sure why a lesser amount got paid with this one.
I personally never faced any problem even by paying the minimum fees for a transaction which did not cause any delay for my transaction, i once transacted around 0.45 bitcoins with the minimum fees of 0.0001 or something and it went fine.
Yes, it sometimes doesn't affect it, but sometimes does.