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