A sketch of a possible reduction to prove that it is NP-complete.
Informally it starts from a modified 3SAT formula used to show that 3SAT is ASP-complete (Another Solution Problem), and "follows" the standard chain of reductions 3SAT=>DIRECTED HAMCYCLE => UNDIRECTED HAMCYCLE => TSP
- Start with a 3SAT formula $\varphi$ with $n$ variables $x_1,...x_n$ and $m$ caluses $C_1,...,C_m$;
- Trasform it to a new formula $\varphi'$ adding a new variable $t$ ...;
- ... and expanding each clause $(x_{i_1} \lor x_{i_2} \lor x_{i_3})$ to $(x_{i_1} \lor x_{i_2} \lor x_{i_3} \lor t)$;
- From $\varphi'$ build the diamonds structure graph $G = \{V,E\}$ used to prove that DIRECTED HAMILTONIAN CYCLE is NP-Complete; suppose that each clause $C_j$ correspond to node $N_j$ in $G$;
- Modify $G$ into graph $G' = \{V',E'\}$ replacing each node $u$ with three linked nodes $u_1, u_2, u_3$ and modify the edges according to the standard reduction used to prove the NP-completeness of UNDIRECTED HAMILTONIAN CYCLE from DIRECTED HAMILTONIAN CYCLE i.e. $u_1$ is the node used for incoming edges, $u_3$ is the node used for outgoing edges;
- Convert the UNDIRECTED HAMILTONIAN CYCLE instance on $G'$ to a TSP instance $T$ in which all edges of $G'$ has weight $w = 1$, except the (unique) edge in the diamond going to the "positive" assignment of $t$ which has weight $w = 2$ (red edge in the figure below); finally the edges added to make $G'$ complete have weight $w = 3$.
Clearly the TSP instance $T$ has a simple cycle that visits all nodes which corresponds to the satisfying assignment of $\varphi'$ in which $t = true$ (and this tour can be easily constructed in polynomial time), but it has total weight $|V'|+1$ (because it uses the edge that correspond to the assignment $t = true$ that has weight 2). $T$ has another simple cycle that visits all nodes with a lower total weight $|V'|$ if and only if the edge of weight $2$ that corresponds to the assignment $t = true$ is not used; or equivalently if and only if there is another satisfying assignment of $\varphi'$ in which
$t = false$ ; but this can be true if and only if the original formula $\varphi$ is satisfiable.
I'll think more about it, and I'll write a formal proof (if it doesn't turn out to be wrong :-).
Let me know if you need further details about one or more of the above passages.
As noted by domotorp an interesting consequence is that the following problem is NP-complete: Given a graph $G$ and an Hamiltonian path in it, does $G$ have an Hamiltonian cycle?
