You talked about "shocking failures to understand CS basics." What would you recommend learning for someone like me before they start an MS in BS?
So I think you're the perfect candidate for an MS in CS.
What worries me more are the options mentioned in the article and the comments for non-CS/informatics degrees to do an MS in CS. Maybe there is some thinking that someone with a BS degree in any science shouldn't have to do undergrad CS work, but it seems to me they should earn a BS in CS not an MS. I also get that some cross-pollination between similar fields (say robotics and CS, applied math and CS, etc.) can be beneficial to the students and the program in general, but make those students take extra undergad courses to catch up. Dumbing down MS coursework for non-CS people really defeats the purpose of the MS for everyone. That would be my main issue with the topics in the article (having a research-oriented and a non-research MS seems fine to me).
That said, it was different than Computer Science. Besides one introductory programming course, there was no programming required. Even for our capstone projects, wireframes were sufficient. We didn't actually need to code anything.
To give you an idea, here's the curriculum: http://ischool.uw.edu/academics/informatics/curriculum
My main concern with doing an MS in CS is that I wasn't exposed to a lot of traditional computer science concepts, such as operating systems, hardware, compilers, algorithms, etc. And the highest level of math I've taken is Calculus I (and a 300-level statistics course which was frankly a joke).
To take a recent example here on HN: did you cover big-O notation? To me that is fundamental, and the BS programs are cutting corners if they're leaving that out.
I'm generally worried about two points I'm deficient in: subjects that require formal education (I don't know if I can learn about compilers on my own, for example), and subjects that require advanced math.
A student ought to have studied and understand discrete math, data structures, and fundamental concepts of computing and programming languages. CS isn't about programming, but for your mind to be in the right place and in order to participate in the program you really ought to be a strong coder with at least one language under your belt. Research will almost certainly require significant coding, even if the work is theoretical in nature.
Beyond that it really depends on what program you're doing and what your focus will be. In many cases you'll want significant mathematics background, including areas like abstract algebra (important for crypto studies), numerical analysis, experience with proofs (useful for theory of computations studies)...it goes on and on.