Bitpay will convert to USD, MXN, CAD, EUR and GBP   ...we only accept fiat if you first use it to buy Bitcoins

I think many people are trying to tackle that one in various ways.  When people ask if we'll accept this or that currency, our standard response is that we use bitcoin for the actual transaction because it has the most secure network behind it (if that ever stops being the case we might consider an alternative)...so, the solution then from a usability perspective is to just make it easier on the sending side to convert from other currencies into Bitcoin.  Whether you have dollars, euros, litecoins or whatever, you can use them to buy stuff with Bitpay if you first convert them into Bitcoin, and software should make that really easy in the future.

With Mt. Gox you can get conversion on arrival of USDs to BTCs, or from BTCs to USDs because that exchange allows order sizes that exceed available funds.  So when the funds arrive, they are automatically traded against the open, unfilled or partially filled order that is outstanding.

Also, their merchant services tool has an "autosell" flag so that the funds are automatically converted to fiat, without having to mess with leaving an outstanding order.