The "its not consistent or logical for you to know X then forget X when you level up" argument fails to convince me for these two simple reasons:
1. Its never logical to suddenly learn or suddenly forget something upon leveling up, because leveling up happens instantly and learning skills takes time. This insight, while accurate, is something you basically have to get over if you want to play D&D. So I find bringing it up to be kind of trite.
2. No ruleset can ever prohibit all forms of verisimilitude-breaking behavior. Its not possible, because rulebooks are small and the player creativity is huge. As such, it is at least partially the responsibility of the DM and the players not to intentionally break verisimilitude.
So while I feel kind of bothered by the idea of High-Climbin' Carl, the best mountain climber in the land, retraining his feats and forgetting how to climb mountains (without in game justification), well, who's fault is that? The game, for failing to forbid this? Or Carl's player?
Given the many advantages of retraining as a game element, the many logical and reasonable ways it can be used, and the fact that Carl's player had to intentionally select to break verisimilitude in this way, I blame him.
The only thing that bugs me about retraining is that I don't really like the idea of retraining heroic feats into paragon feats. I kind of wish that they all lived in their own little boxes. Because if they don't, then eventually, as more feats come out, we're going to start abandoning wholesale all the heroic tier feats in exchange for paragon, and then again in exchange for epic, since there will be options for feats that are similar, but better. I don't like the idea of material becoming obsolete like that as you level up.