I think mycelium needs to improve the way it calculates fees. I submitted a transaction with the "normal" fee. It took an hour to get the first confirmation.
d75f3a16f84351a7cb23e24c0b082b8acb5ce4bc33f28fbe5a77a738842020bb
There were 50 minutes without a block at that time.
That just happens, 10 minutes between blocks is only the average, it can sometimes be faster or slower.