Are you sure you are on a *nix server? If you are then they could have Mod_rewite disabled.
Are sure that you have your htaccess right, named ".htaccess" without the quotes. Uploaded it as plain text, you don't have the frontpage crap installed on your server?