I had this problem too, its been 9 months, but im sure you or someone else will find this valuable, so everyone I will tell you what you need to do if you have this problem so listen up.
1) The problem is b/c you changed the permalink from default to whatever you chose, BUT your htaccess file was not "writable".
So what you need to do, is FTP you site, find your htaccess file (its under public_html). Right click on it (i use filezila) select file permisions, then check off read,write,execute for everything. The important this is to change "file permisions" for the htaccess file.
It will make more sense once you do it. Then go back in to WP, select setting -permalink, re-select your option, and save it. You should be all set, it should be http://www.yourdomain.com/feed. You should not get a 404 error anymore.
Hope that helps!