404 Error on all Pages

1) Update your pretty permalinks from the admin

recheck

2) Confirm you have a .htaccess file in the root of your WordPress installation.

3) If above Yes post the contents here if no then manually create one:

http://codex.wordpress.org/Using_Permalinks#Creating_and_editing_.28.htaccess.29