It’s on the same host?
Check the .htaccess file on the blog directory of the host you’ve been experiencing problems with. It should have this code written:
<IfModule mod_rewrite.c>
RewriteEngine On
RewriteBase /
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /index.php [L]
</IfModule>
(“RewriteBase /” and if you are using it the blog in the root of the website; if it is a folder inside the website, write its path there, as “/blog/”, if the folder is named “blog”; in this case, change also: “RewriteRule . /blog/index.php”).
If you dont see that code in the file, insert it manually and upload the file back to your blog directory. If you dont find any .htaccess file at all, create a text file, add the code above, upload to your blog directory and rename the file to “.htaccess”.
If your host doesnt allow you to add .htaccess files, you’d have to use “almost pretty links” instead of real pretty ones.
Example of an almost pretty link setting: /index.php/%post_id%/%postname%/
(it should start with “/index.php/”, the rest is up to you).
Cheers