Zurai said:
Right. So how do you re-flavor the desert nomad fighter who's never seen more than a wellful of water in his life taking to water like a fish the first time he sees the ocean?
Character talking to himself: Alright Regar, keep calm, steady, don't panic. This stuff is weird, but think of it like quickstand, just have to pull yourself through it, one arm at a time. Remember that oasis you were at last year, it like that....just a LOT bigger. That's right, one arm at a time. Kicking seems to help, kick harder. Alright, your doing this, just keep going. Go!!
In all seriousness, swimming isn't that hard, even a baby knows instinctively to hold its breath underwater. The reason people have a hard time of it is that they panic, they are afraid of the water for obvious reasons. High level heroes don't just panic, they are cool under pressure, they work through problems instead of running kicking and screaming.
If I met a desert nomad who could control his fear, I could teach him the basics of swimming in 5 minutes. For most people, its getting over the fear that takes the longest. And if the guy had lived in a harsh desert environment, he's likely in GREAT shape. Endurance helps in swimming a lot, but aerobic and musclar endurance. A high level fighter is going to have those, and for wizards you can flavor it the way I mentioned.
However, how about this scenario:
"Hey what happened to Regar?"
"You mean the oath keeper of Valimar, the slayer of Cortees, the greatest champion of the seven kingdoms? Drowned in a pond."
Isn't it a bit better to try and flavor why a high level adventurer can do stuff then say he can't and let him struggle like an incompetent boob?