This is likely related to a problem with the plugin itself, or a conflict with another plugin.
The other thing to check would be that your .htaccess file exists and is writable by WordPress. Permissions of 644 are what is recommended see this codex entry.
Ownership of the .htaccess file would generally need to be the apache user (sometimes this is www, on CPanel its usually nobody, but that will vary by web host or Operating System). If you’re running on Windows, that is another story.
There is another decent article about .htaccess permissions here.
For posterity, here is how to change permissions and ownership of the htaccess file:
chmod 644 .htaccess
chown apacheuser:apacheuser .htaccess
You can usually find out permissions and ownership in your website’s root by using this command:
ls -l
Remember to be careful when changing ownership and permissions and consult with your hosting company if you are at all unsure of what you’re doing.