I tried the usual drill (set permalinks to default, delete .htaccess file, set permalinks to custom) but no matter what I did, WordPress would just create the .htaccess file and then not write anything in it!
I solved my permalinks problem by adding the following code to .htaccess (my blog is right under /public_html/:
# BEGIN WordPress
<IfModule mod_rewrite.c>
RewriteEngine On
RewriteBase /
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /index.php [L]
</IfModule>
# END WordPress