Permalinks and The Network Theme

I have tried to use Permalinks with this theme and when I change it I cannot preview my pages and the site comes up with 404 errors on every page. Everything is updated. This is a staged site. I have not had this problem with other staged sites or with other themes I have worked with from WPMU. I am looking for suggestions or direction with this problem.