We think that problem is in mod_rewrite configuration in .htaccess file or you don't have mod_rewrite at your server at all (then you need to ask for it your server administrator or change it in server configuration if You have access to it). If mod_rewrite is available, try to add after line "RewriteEngine On" the following line:
RewriteBase /
or if it won't work and your shop is in subdirectory, you can try add
RewriteBase /subdirectory_name/

On some servers, problem is caused by first line in .htaccess file:
Options +FollowSymLinks
You can try to remove it.

Unfortunately it works different at various servers, so there is no one solution. If tips we wrote won't work, please send us data for ftp connection, so we may look at your server and find the reason.