You can try the following:
1. From the FTP access your .htaccess file and give it full permission 777 .
2. Now open the .htaccess file in notepad (gedit in linux) and insert the following code
# 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
3. Now, reupload the file to the root folder.
4. Now try changing the permalink.
The above is applicable for Linux hosting. If you are using windows hosting then install this plugin -> http://wordpress.org/extend/plugins/wp-htaccess-control/