I had the same problem. It sounds like you don’t have rewrites turned on in your installation.
Find your httpd.conf file, find the following line:
#LoadModule rewrite_module modules/mod_rewrite.so
And remove the # at the beginning so it looks like this:
LoadModule rewrite_module modules/mod_rewrite.so
Save and then restart the service. Custom Permalinks should now work. There might be an easier way but I’m not familiar with Linux