As far as a full curriculum goes, I don't believe there is one that does exactly what you want. Books (in the United States, at least) divide into two camps:
"Constructivist" (e.g. Everyday Math, Connected Math)
"Traditional" (e.g. Saxon, Singapore)
Now, any search you make that even has a whiff of these terms will summon up loud and angry missives (try this article from the New York Times for an idea).
Constructivist curriculum is an attempt to catch the "joy of mathematics" approach to learning; for example rather than a worksheet with addition problems there might be a question about all the different possible sets of numbers that add up to 20.
The downside (as pointed out by the article above) is that (especially when taught by teachers who aren't themselves strong in mathematics) it can lead to basic skills being missed.
This is a problem Lockheart's Lament acknowledges. He seems to think students won't miss anything important. This can be true if the person steering the education is a mathematician, but with a non-specialist (i.e. most elementary school educators and homeschoolers) things can go horribly wrong.
Now, it's possible to balance to pull off a fantastic curriculum, but the ones I know about (say, at the Russian School of Mathematics in Boston) are, as self-described by the teachers, not following a curriculum at all. That's great if the teachers are experts, but put homeschoolers in a quandry.
I think the world is still waiting for an inquiry-type elementary curriculum that can be followed by non-experts and doesn't shortchange basic skills. So for now I'd suggest:
a.) Pick a traditional curriculum (Singapore is fine, although do shop around).
b.) Supplement. This very question is filling with lots of suggestions.
The topic you touch upon is vast, but I wanted to comment on this phrase: "problem/solution patterns which is very different from showing them the underlying conceptual tapestry".
If for some reason you have to use this format (department restrictions or whatnot) choosing your problems well will simultaneously introduce some of the conceptual tapestry. Rather than introducing a mathematical tool and then the problem that goes with it, you introduce the problem first (just out of range of the student ability) and bring it to the point where things get stuck, where something new is needed to go further. Then the motivation is clear for the new tool.
Best Answer
I cut my teeth on an 80's version of Differential Equations and Their Applications: An Introduction to Applied Mathematics by Martin Braun . Amazon lists copies as going for under $50. Perhaps someone from this millenium can say if the new editions are still good. I liked the anecdote about the Tacoma Narrows Bridge, and found many of his examples well motivated.
Gerhard "Ask Me About System Design" Paseman, 2010.04.15