Relevant quote:

"Anyone who cannot cope with mathematics is not fully human. At best, he is a tolerable subhuman who has learned to wear his shoes, bathe, and not make messes in the house." -Robert Heinlein

This quote is harsh enough that I feel the need to say that this is one of Heinlein's characters talking.

Although the whole "innumerates are terrible" thing appears all over his books.

Agreed. It is harsh.

Why should they be embarrassed? It is the inability of Math teachers to instruct those who have difficulty with Mathematics.

Aren’t K12 schools teaching “new math” or whatever fad, to students and focusing on teaching to a test due to no child left behind?

I wonder what studies have been done to measure how many students are math deficient in general population.

Furthermore, what are approaches that could remediate such issues?

Indeed. People are embarrassed to admit that they're illiterate, but somehow it's different when it comes to math.