I've check with my host and they do have mod_rewrite installed.
I've checked that there's a .htaccess file (there's also a htaccess.txt, does that matter)
Happens on a completely clean install as well as my modded version with xen porta and plugins.
Any ideas?