The problem is not with the 4051, but rather that the PWM (pseudo analog out) isn't fast enough to render a "true partial voltage" to each LED in the time you need to scan across them to keep persistence of vision intact.
Not that I know what you did and how you did it, but that's probably not what happened. More likely the PWM is not synchronized to the display multiplexing, causing no end to flicker. It could work (maybe) if if the PWM frequency was "really fast", compared to the display multiplexing, AND if the frequency difference is not within something visually noticeable (again causing flicker).
But that's not how it's normally done. To multiplex PWM signals, they should be syncronized to the display. IE make your own PWM multiplexing, don't use the built-in PWM (unless you can sync it somehow).
Now, my next goal is to use a D-to-A converter to send the true voltages to the 4051. That should clear that up (by circumventing PWM at the cost of using more digital lines for the d-to-a) and allow me to get shades of "grey" on my matrix.
Ok, I'm not saying using some DAC scheme to make different shades of LED light is impossible, but I would say it is "not likely"! That is an unusual, or rather impractical way to dim LEDs because it is difficult to get right (as in linearly increasing light output with each DAC step). For one thing a LED is not linear. Even if the light output might be somewhat linear to the electric current through it (but probably not quite, which further complicates matter, depending on the LED of course), the voltage-current relationship is not. It is like a typical diode curve with a threshold voltage to turn it on. Also, given small differences in this threshold region between "identical" LEDs, it would be difficult indeed to get multiple LEDs evenly lit.
In other words, while it might be easy(ish) to get it from the brightest to more dim, I imagine the hardest part would be from that "more dim" point to to completely off (if that made any sense).
I would suggest you start with a "simple" 8x8 display before you tackle an 8x8x8 one, especially if you want gray shades. Btw, imho it is very feasible on the 8x8, to a point, I doubt it is on an 8x8x8.
EDIT: It's not that I don't think one can't get any PWM steps in an 8³ cube, I just doubt one can get very many.