Did you get a message like “If your .htaccess file were writable, we could do this automatically, but it isn’t…” when you tried to change the permalinks?
If not, have a look at your actual .htaccess file and make sure that 1) it’s writable and 2) that it includes a bit of code that begins
# BEGIN WordPress
It sounds like WP isn’t able to write the redirect rules to it.