When I try to change my permalink settings from Plain to any of the other options, all pages but the homepage then say that the page is not found. I have already tried deleting the .htaccess file so that it re-generat...
What you would need to check is the following.
Make sure that Apache mod_rewrite is enabled, you can check that with this command:
apachectl -M | grep -i rewrite
If you don't see the module, you can enable it...