During the hosting migration a wordpress cms, there was a problem with permalinks and postnames, when you try to access a random categories the error 404 not found appears.
To solve the problem make sure your virtualhost looks like that.
Options +FollowSymlinks
AllowOverride All
Order allow,deny
Allow from all
In the wordpress cms, navigate to Tools->Permalinks->Custom Structur ( /%postname%/ )
This is output generated from wordpress cms .htaccess file
BEGIN WordPress
RewriteEngine On
RewriteBase /
RewriteRule ^index\.php$ - [L]
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /index.php [L]
# END WordPress