Is this running on an Apache server? In that case you need to make sure you have the mod_rewrite module installed and enabled.
I'll assume you are running on a linux system here so you can activate the mod_rewrite module in a way similar to this (directories etc might be different). I also assume you are running the latest apache2 here, things might be different for older versions of apache;
Code:
ln -s /etc/apache2/mods-available/rewrite.load /etc/apache2/mods-enabled/rewrite.load
apache2ctl restart
This will create a symbolic link from the /mods-available directory to the /mods-enabled directory for rewrite.load, which when apache starts should then load mod_rewrite. After that Wordpress should take care of everything else.