In general, I think this is a topology problem. The destination node cannot be reached from the source node. According to its documentation, v.net.salesman
calculates the optimal route to visit nodes on a vector network
By definition of the traveling salesman problem, this route is a tour that must be connected. So, as the message suggests, if one of the nodes is unreachable from another, i.e. if two nodes are on two components of the graph, no tour can be constructed.
The fact that
v.net.salesman worked on another set of nodes means that those nodes are in one component of the graph. It doesn't guarantee that the current set of nodes are in the same component.
You probably know the cause already. I can't speak for QGIS/GRASS. But at least I know you can use ArcGIS to identify the problem (I guess there should be a similar solution in QGIS/GRASS):
You can compute single source shortest path from each of the two nodes, respectively, by constructing a (Geomertic) network. Then looking at the distance label for network nodes, you can see the components that these two nodes resides in respectively. From there, maybe you can figure out the spot at which the network is disconnected, and move and snap features to connect the two components (if it's a data quality issue). Or if one of the nodes is just not snapped to the network, you can snap it to the network.
-- EDIT --
To clarify, you can e.g. compute network accessibility from each of the two nodes and generate buffers like this in the ESRI website:
Then by observing the shape of the buffer of a large distance, you will be able to see if one of the nodes in question is isolated from the rest of the network or identify the problem site on the graph. While I am not familiar with QGIS/GRASS, I don't believe Open Source GIS should have a problem computing shortest paths. The principle is the same. That is, in essence, you can diagnose the topological problem by checking connectivity between the problem nodes.
While tools like
v.clean can sometimes fix the problem automatically, e.g. by breaking lines at each intersection, they might occasionally be topologically incorrect e.g. by confusing an overpass with an at-grade intersection or by snapping features incorrectly, giving you infeasible routes. But I guess one can always visually investigate the changes made by an automatic cleaning and determine if they are appropriate.