However, while that's all fine and dandy, index.php isn't getting control of the request.
Which is evident since the "usual" apache error is being displayed instead of the usual WP 404.
Here's what goes down on a request, in a nutshell.
It comes in, apache checks the .htaccess file if there is one. There is in this case.
According to the .htaccess file, it first cleans the www out of the url if it exists.
Next, it looks to see if it's a request for a file from someones "files" directory. If that is true, then it passes control over to blogs.php with parameters to allow it to serve the correct file.
If that isn't the case, then it looks to see if the request is for a legitimate file or directory. Meaning, it physically exists on the box.
If that isn't the case, then it looks to see if the request is for a wp- type file (wp-signup, wp-activate, etc). And either passes control to it, or keeps moving on to the final "if all else fails" option.
Hand control over to index.php, and let it figure out what to do with the request.
In the case of a permalink, as per your example, control should be passed to index.php for it to work it's "magic" and pull up the content.
However, it isn't being given the chance to do so. This is evident by apache producing the 404.
Essentially, what's going on isn't being caused by MU, or so it seems. It's something in the set up, configuration, or something like that.
That being said, exactly what's going on here? How is it set up? How are you accessing it? With what domain?
If you're running subdirectories, vice a subdomain install (although subdomains are recommended), then you don't need any of the wildcard stuff. It says so in the readme file.
If you were trying subdomains, on Apache 2 you wouldn't be adding the wildcard stuff to the httpd.conf file, as that's not where the virtual directories are handled in A2 to begin with.
So, at this point, I'm inclined to put the mark on the server and its not being properly setup and configured.
Without being able to see the site you're trying to put together, to see what's happening on the pages and what's going on, there isn't much help that can be given because anything is purely a "guess".
If you need help, cool. But you have to help us help you. And being secretive doesn't cut it when something is wrong and you need some help. If we can't see the problem, then any type of a solution that ends up working is due to a lucky guess.