This is a pretty funny claim to see made about one of the most famous NP-complete problems there is. As thelema314 points out, the usual certificate verifies "is this path shorter than a threshold?".
Usually, the problem is simplified to a threshold test, like: Does this tour have path length < X? These kind of problems are equivalently difficult to produce solutions for in the general case, but are straightforward to verify.
For Traveling Salesman, this means that given the best tour for an N-city graph, the best tour for the same graph augmented by a single vertex could be entirely different.
And this is easy to then contrast with, say, sorting, to counter the earlier objection.
We can split the set into two, sort the two parts individually and then trivially merge the results. We cannot split the cities into two, solve the traveling salesman problem, and then easily merge the results.
And adding a new element to a sorted list is just a linear insertion.
Here is an obvious difference:
In sorting, we have locally correct solutions in that given any two distinct elements a, b out of the N, we know whether a is to the left or to the right of b in the final order. Moreover, for a given a, we can find, in linear time, the smallest b which is greater than a: a's successor in the sorted order. Thus sorting is no worse than quadratic. Also, we can examine any permutation of the N items and tell in one pass whether or not it is in sorted order. So recognizing solutions to the sorting problem is linear.
Given any two cities, a and b out of N, we do not know which one is visited first in the shortest path, and we certainly don't know what a's successor will be in the solution. Even verifying a solution to the problem (Is this sequence of cities the shortest path?) cannot be done in polynomial time.
So, yes, the mere fact that there are N! orders to search through is by itself unconvincing about the hardness of the problem.
Lectures on it would be easy if that were the case: Good morning everyone; today we discuss a class of so-called "NP hard" problems, which occur whenever there is a combinatorial explosion in a search space. :)