Permalinks Broken

Suddenly all my permalinks stopped working. I can access the posts from the Dashboard editor but ALL of the links produce a 404 (404 Not Found error was encountered while trying to use an ErrorDocument to handle the request.)

This only happens on this blog, not on my other ( Both blogs use the same provider (though different servers) and have WPMU installed.

!!! While not comfortable going into the htaccess file I followed the suggestion of and added some code to the WordPress section and it fixed the problem. Sorry for the false alarm.