Did you update your .htaccess file? Do you have one? If so, are the permissions set so that’s it’s writeable? if your .htacces files isn’t there, or isn’t writeable, then the *database* will be set to change the permalinks, but it won’t take effect because the necessary changes didn’t make it to the .htaccess file – thus, 404 links.
I have similar problem. I’ve chosen to use permalinks, but I get only 404 pages.
1) Godaddy says my Linux server has rewrite_mod enabled
2) I have .htaccess file and it seems to be written correctly by the system (I’ve uploaded an empty file and now the code is all there)
3) The chmod for the .htacccess was 666 and 777 and even with so many permissions, it hasn’t made it work)
My website: http://www.bonato.cc
Hey! Forget it! Maybe my WordPress install got scared of this “public complaint” and decided to work! It suddenly made the permalinks alive.