Be a Rebel

If wordpress permlinks are not working for you, the first thing you should check is if mod_rewrite module is enabled! Learned this the hard way.
How to check:
Run phpinfo() and in Loaded Modules sections the mod_rewrite should be present. Just do a CTRL-F after running phpinfo() and check if it finds mod_rewrite

Loaded Modules

core mod_access_compat mod_so http_core prefork mod_unixd mod_systemd mod_actions mod_alias mod_auth_basic mod_authn_file mod_authz_host mod_authz_groupfile mod_authz_user mod_autoindex mod_cgi mod_dir mod_env mod_expires mod_include mod_log_config mod_mime mod_negotiation mod_setenvif mod_ssl mod_userdir mod_php5 mod_reqtimeout mod_authn_core mod_authz_core

So, if it is not there, edit your /etc/sysconfig/apache2 and add “rewrite” to APACHE_MODULES

APACHE_MODULES="actions alias auth_basic authn_file authz_host authz_groupfile  authz_user autoindex cgi dir env expires include log_config mime negotiation setenvif ssl userdir php5 reqtimeout authn_core authz_core rewrite"

Restart your apache2 server, if it starts without any errors, run phpinfo. mod_rewrite should be there now!