Hey there Justpaulo,
Had the same problem as you did, managed fixing it this way..
1. Disable ALL plugins
2. Log into your server via sFTP/SSH/FTP and find your .htaccess file in the directory of the wordpress installation.
4. rename or back up
5. Go back to wp-admin and visit your permalinks page. enable custom permalinks with /%postname%/
6. reactivate plugins
This seemed to fix the issues I was having with permalinks.
