0.0001 gets me very high priority on most of my transactions. If they were higher value Tx, I would include more of a fee.

I use BC.I quite a bit and have not had the OP's problem. However, I read a similar thread several months ago that described a similar issue. I have paid VERY close attention since then.

This was likely OP error all the way. If the OP can track the miner down, I'm certain he will get a refund. We bitcoiners are like that.