Problem NP-complete for Euclidean geometry but in P for Non-Euclidean geometry?
Partial answer:

Maximum TSP is polynomial time solvable under polyhedral norms,
but NP-hard for Euclidean norms (optimization as well as decision
version). Whether the latter is also NP-easy is a different question.
(You might be able to define a somewhat artifical variant that is in NP,
since the instances created for the NP-hardness proof only require
bounded precision.)

A. Barvinok, S. P. Fekete, D. S. Johnson, A. Tamir, 
G. J. Woeginger, and R. Wodroofe.
The geometric maximum Traveling Salesman problem.
Journal of the ACM, 50:641-664, 2003.