Page links totally broken with WPMU NELO

The page links appear to be totally broken on this site. Many of the pages are now reading with an error 404 code and this (see attached).

I've got business pages and Local Offers now, all built with pages which are showing error messages about not being able to find.

What can I do to fix this asap, as I have QR codes pointing to these pages??

If I change themes will this affect the function of these pages? It shouldn't.. right?