I had same problem. My .htaccess file was CHMODded to 644: disallowing WordPress to successfully edit it (that is good if permalinks is working!)
How to Fix It!
To remedy this problem I simply changed the file attributes of .htaccess in my FTP program to 666. Then I went back to my permalinks page and chose the link structure I wanted and saved it.
Now, it works!
Don’t forget to set your .htaccess file back to 644 – otherwise, it’s a security risk!
Hope this works for you too. English is not my mother language, so feel free to ask if something sounds “strange” to you. ??