You still have conversion fees but you might have a lower conversion fee when using Bitcoin as the medium between the two currencies.
The reason you pay high fees when you are using currency conversion when traveling is that currency exchange can be an expensive service to provide. Your hotel taking your foreign currency must then get those funds converted back to their local currency -- something that is not cheap to do. Or a Travelex pays expensive rents in airports or other retail locations near lots of travelers and pays staff so their fees are high as well.
Bitcoin makes it so that only the local (domestic) currency would be used on both ends. Before leaving on a trip you perform a domestic transaction to convert your local currency to bitcoins, and then on arrival at your destination you can convert bitcoins to the local currency there.
But the problem is there are not yet many local traders who perform this service. LocalBitcoins is growing quickly and it is getting easier to do a trade (and at a lesser price premium) however when you arrive at your destination you probably aren't wanting to spend your time trying to figure out how to cash out your bitcoins for local currency.
It is a chicken and egg problem. When there are a lot more people with that need, there will be more and more people offering that service. When there are more and more people offering that service, there will be more people willing to rely on that as an alternative to cash conversion at hotels or through services like Travelex.
If you line up a trade in advance, it can be just as convenient as any other method of doing foreign currency exchange.