The subsets are interchangeable....
...at the points at which they intersect (i.e. overlap).
Or do I need to put this in plain English, Wall and Fence are bundles of abstract concepts. Many of the ideas they convey overlap. When the emphasis is on the overlapping concept, then, yes, they may be used interchangeably without a disruption in the connotation. If, however, you step outside of the overlapping subset and want to indicate meaning that falls outside of the region of intersection, then one term or the other becomes the proper term to use.
In the current case, the emphasis is not on the physical attribute of the Wall or Fence. It is on the divisiveness that the barrier presents. Because the emphasis is on the "Act of Division", not the "Specific Property of the Division", Wall can be acceptably substituted for Fence to convey the true divisiveness of the barrier. As I implied previoously, fence has connotations of a more porous barrier - fences make good neighbors. Whereas wall has connotations of a non-porous border. So, if you want to convey the idea that the barrier was non-porous, you may choose to call it a wall. If you want to convey the idea that it was porous, you may call it a fence.
Since you have chosen to ignore the concept of words as Sets, I can only conclude that you are stubbornly clinging to a viewpoint that is strictly boolean logic - it's either a fence or a wall, therefore its either a true statement or a false statement - either he is telling the truth or he is lying. Boolean logic works in limited circumstances, but it can easily be misapplied when extended beyond that domain.
Of course, this whole fiasco could be solved by simply ascertaining some more facts - i.e. asking questions, cross-examination, etc... But since you want to base your rant on a single word, there's not much chance for illumination. You have made your conclusion and stuck with it, based on the tiniest shred of evidence. That evidence is not convincing and the conclusion that you draw is not grounded in logic - Ipso Facto - you are being illogical.
If you do, we can move on to the next point.
The next point in your dialectic was that because he called it a Wall, that this logically necessitated the specific conclusion that he is lying about being there.
Faulty logic. Plain and simple. The logic being examined is:
General Premise: he said there was a wall
Specific Instance: It was a fence
Specific Conclusion: he was not there
Right now you are quibbling about whether the general premise has been established. I am also denying that the specific conclusion is necessitated, even if we assume that the general premise and specific instance is a given. There are a variery of rational explanations which can easily account for the fact your logic does not hold.
Ironically, he said there was a FUCKING WALL, but I haven't seen you jump on the fact that the barrier at the border has never been known to copulate.