Yes, it's similar to the fallacy committed when people say "I have reduced my problem to an instance of graph colouring, therefore my problem is NP-complete."
You have it the opposite way, if you can reduce an instance of an NP-complete problem to your problem, then your problem is NP-complete. Is that what you meant by a fallacy?
That's the difference between theory and real world. In theory something may not be perfect, but it's still good enough for practical use.
For instance, planetary motion is not really well described without solving N-body problems and taking relativity into account, and yet Newtonian dynamics and slide rules were enough to land us on the Moon.
I agree with your basic point, but i think it's not about theory vs. the real world so much as confusing the worst case for the practical case.
I often think that approximation algorithms, randomization algorithms, fixed-parameter tractability and "special case" deterministic algorithms are what people should look at if they are interested in positive solutions (as opposed to lower bounds). Not to mention the incredible success of SAT solvers.
Well there's two problems there: you can easily "reduce" a P problem to an NP-complete one; it's when you do it the other way around (reduce graph coloring to an instance of problem X) that you even have anything to worry about. But yes, worst time bounds for many problems are devilishly hard to achieve even when you're trying.
