Are there NP-Hard or NP-Complete problems that humans a really good at solving?
With regard to the relationship between the brain and complexity theory, I think it's important to remember that the brain hardly ever comes up with exact solutions to problems and seems to prefer inductive reasoning to deduction. (How to induce a minesweeper strategy computationally) Furthermore, we mostly conjure up approximations. Précis of Bayesian Rationality: The Probabilistic Approach to Human Reasoning discusses problem solving in inexact (probabilistic) terms. I believe that one of the follow-up articles (Identifying the optimal response is not a necessary step toward explaining function, page 85) is relevant to your question:

"An explanation requiring an optimal response function must also
consider that: (e) for problems of inductive inference, the optimal
response is often analytically intractable to determine with exact
methods, and will not be unique; (f) behavioral responses are typically
approximately optimal, revealing a tendency rather than a
correspondence"