Bumerangas,
Edit your .htaccess file (it’s in your domain’s root directory, same place as index.php and /wp-content etc…). Add these lines to it:
DirectoryIndex index.php
# BEGIN WordPress
<IfModule mod_rewrite.c>
RewriteEngine On
RewriteBase /
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /index.php [L]
</IfModule>
# END WordPress
Make sure you leave a carriage return after the final line (press Enter/Return). Then change the .htaccess file’s permissions to 777 (Read, Write and Execute for all users). In fact, it should be fine (and safer) at 644.
Once done, re-activate the plugin and you should be good to go.