You only paid 0.00004195BTC fee for 373 bytes transaction, of course it'll take long. If you've sent many transactions like that and never got this problem then that's what's surprising.
As I said I typically pay whatever fee the core client suggests, and that is what I did here.
So if you click the Choose... button next to Transaction Fee, you will get some more detailed selection about the transaction fee. The normal fee (which is probably what you have it set to), is actually an estimate to get a confirmation within the next 25 blocks. So if you actually want faster confirmations, you need to move the slider to the right towards "fast".
Moreover blockchain.info describes expected confirmation for this transaction as "Very Soon (High Priority)"
- though I do not know on what basis it makes that assessment.
Their assessment is highly inaccurate. I recommend that completely disregard it and never think of it again.
Well yes I understand that thank you but given the number of full blocks we have seen in quick succession (there have now been 8 blocks exceeding 998 kB) I imagine the backlog of transactions must be quite large, and how much extra would one have to pay to actually make a difference?
You just need to pay more than the lowest paying transaction in the block. You would effectively bump that transaction out with yours.
