I think a lot of it comes down to establishing a set of tools that can be used for whatever problem you encounter. No matter the language or the problem you want to have at least a vague idea of how it might actually work. Further, when you in inherit a code base, you want to have the tools to dig in and find out how the thing works. And when problems arise, you want to be able to get inside the black box and ask things like "Does this result make sense."
A big missing piece in a CS degree is an understanding of the SDLC. The use of svn, tagging and build scripts is essential to any software development effort, and yet it is rarely mentioned. Creating elegant algorithms is great fun, but when the client is screaming that the code doesn't work and all you can say is "works on my machine", you'll wish you had the warm blanket of a proper build process.
I will say, however, that a CS degree does provide the basic programming and debugging skills necessary for a career in software engineering. The downside is that a 4 year degree is quite pricey, and much of the content of a CS degree is more theoretical and less applied.
I recently had an interesting conversation where a fellow programmer made the argument that CS was splitting into two branches, much like mathematics: applied CS and theoretical CS.
I think this is an oversimplification, but largely correct. A traditional CS degree is about 20% programming skills, and then lots of math problems to solve.
The time is ripe for a good software engineering degree (i.e. applied CS), which would be far more valuable in the job market.
It agrees with your points - a split into applied and theoretical would probably be a good thing. The programmers I work with in the UK seem to come from physics/mathematics backgrounds, or electronic engineering, with just a few CS graduates. All of them (even the CS graduates) feel that a large proportion of what they learnt on the degree is irrelevant to their career going forwards. A degree focussing on practical software engineering would probably be very useful!
http://www.google.co.uk/search?q=msc+software+development
These seem to be a good alternative to "computer science" degrees at the same level.
The experience of getting the degree itself though....