WordPress Permalinks 404 Not Found

sounds like a htaccess issue… try a .htaccess file in the wordpress root with the content (which differs in one line from your posted blog):

# BEGIN WordPress
<IfModule mod_rewrite.c>
RewriteEngine On
RewriteBase /
RewriteRule ^index\.php$ - [L]
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /index.php [L]
</IfModule>
# END WordPress

from Using_Permalinks