MU Links to Posts and Pages all result in 404 Errors

We just setup a new server and installed WordPress 3.0. We enabled multisite on this WordPress instance. We added a couple test sites. We noticed that all posts and pages links within the sites results in a 404 error: Not Found The requested URL /2010/11/17/hello-world/ was not found on this server.

Any suggestions on how to resolve this issue would be greatly appreciated.