This could depend on your host server – I used to host my sites on a Zeus server and had this same problem. You’re probably not on a Zeus server, it’s more common to be on Apache. You can check with phpinfo.
Create a file and call it phpinfo.php – include only this:
<?php phpinfo(); ?>
Upload it to your server and navigate to it in your browser (www.example.com/phpinfo.php) – look for Server API, if it’s Apache then we’ll need to look at your .htaccess rewrite rules.
If it’s Zeus then, to my knowledge, you can’t use pretty permalinks.