My web store is not responding at all. All the buttons, footer links, header links, categories show error 404 upon clicking. The theme of the store also appears as list view and I can not even login to my admin page as it shows error 404 not found 1.
Have you tried accessing the links using index.php? :
If you can login using this method, check System->Config->Web-> Search Engines Optimisation. Set it to No and clear cache and reindex.
It might be that you are using mod_rewrite but it is not installed on the server. Clearing cache and reindexing is always the first thing to do anyway.