I think you framed the question well when you asked, "Does this do the work that Kant needs it to do?" However, when you speak of problems being NP-Complete, it sounds like you're perceiving it as a matter of how obvious it is or how easily its truth can be discovered by reason, and I think that misses the point with respect to what Kant actually needed the distinction to do.
One of the things that he needed to do is in consonance with what Quine is asserting: Kant needed the necessity of analytic judgements to be rooted in the tautology of definition as established by convention or agreement. As Quine said, "Functionally a definition is not a premise to theory, but a license for rewriting theory by putting definiens for definiendum or vice versa." ("Truth by Convention") I've already addressed that in more detail in another post.
Another thing he needed to do was to maintain that all synthetic judgements actually assert something, i.e. they must contribute something to the knowledge about the subject. For example, we might propose the following two definitions:
- ∀x[Dx ↔ Ax]
- ∀x[Ex ↔ Ax & Bx]
Given that they are definitions we can assert that they are necessarily true by convention, and they are also vacuous because, being definitions, they contribute nothing to our knowledge, as Quine insists.
It might be argued that they both have the property A in common, so the second definition makes a substantial claim. However, that's not the case at all because, as a definition, it doesn't assert that there is anything that has both the properties A and B, nor does it assert that having property A implies having property B. It only establishes that, by convention, if there should be something that has both properties, then we may refer to it as E. In virtue of that alone is it an analytic proposition.
On the other hand, given the first definition of D, if we were later to assert that ∀x[Dx → Bx], this would be adding to the definition and would thus be a synthetic judgement. We could also conclude that ∀x[Dx → Ax & Bx], which would also be synthetic, because it was not established by convention but by means of another synthetic judgement. What's important to notice here is that ∀x[Dx → Ax & Bx] has a form almost exactly the same as the second definition, but one is synthetic and the other analytic. The difference has nothing to do with content but with how their truth value is established.
Therefore, it can be seen that distinction between analytic and synthetic cannot be discovered on the basis of some empirical or analytical test; rather, it has to be determined according to the conventions of language that we choose to use. Synthetic judgements are those whose truth value depend on something other that mere convention alone.
Concerning mathematics, I believe that Kant was probably mistaken that some propositions of arithmetic are synthetic. However, I believe that he was correct concerning some geometric ones. The difficulty in deciding the question has to do with determining exactly what it means to assert that the forms of intuition can be characterized by a particular system of geometry. However, given that some geometric primitives cannot be defined in a way that is non-circular, I believe that they serve as a basis for certain propositions whose true value can't be attributed to either convention or empirical evidence (the forms of intuition being non-empirical in nature).
(The point of mentioning my opinions about mathematics is not to convince you one way or the other; rather, it's intended to illustrate how the analytic-synthetic distinction might be applied to Kantian questions.)