I’ll also add another solution (a little silly) to this post, since I was stumped for a while…
I thought I was updating my .htaccess file by dragging and dropping it into my FTP program, but it wasn’t updating. I found this out by, in my FTP program, by turning on “show invisible files”. Then I edited the .htaccess file directly within my FTP program. After saving, it worked.
And for the record, webhostingpad.com by default always has “AllowOverride” set to “All”, so there should be no need to edit it (because you can’t).
The .htaccess file comes with the Starterkit. Since it starts with a dot, it is usually a hidden file in the file system, and you might have missed it. You have to deploy it on the server along with the other files, i.e. next to the index.php etc.
On a Mac, you can make them visible with CMD + Shift + .