Try this - after activating the plugin, go to the Settings menu in WordPress then click on the Permalinks submenu. Without changing anything, click the Save button at the bottom.
If you get a message saying "You must now update your .htaccess file" (or something to that effect) then it means your .htaccess file isn't writable and therefore this plugin needs an extra step to work.
Copy and paste the code you get given into your .htaccess file in the root of your WordPress installation (or create one if it's not already there). If you don't know what this means there are plenty of tutorials on the web about .htaccess.
Once you've done this and saved your .htaccess file, try uploading again.
If it works, great. If it doesn't, then you have a problem which I've not come across before.
Hope this helps!