Hi Duarte,
You don't mention which Moodle version you are using, but I'm sure you must be working with some 1.9.x version (because the admin role works differently in 2.x).
I guess you don't have a full backup that you could use to restore your site, do you?
Anyway, don't worry, as you'll be able to fix this in a few easy steps (assuming that you are working with a MySQL database and that you can access it via phpMyAdmin), but first, some background info...
The mdl_role_capabilities table has 13 registers (on a 1.9.13+ Moodle installation, and 50 on 2.0.4+ installation) for an unaltered Authenticated user role (roleid=7).
When a capability is set to:
* Not set, the corresponding register is deleted.
* Allow, the permission field is set to 1.
* Prevent, the permission field is set to -1.
* Prohibit, the permission field is set to -1000
So, to fix this problem:
1. Go into your phpMyAdmin, select your database and the mdl_role_capabilities table.
2. Click on the SQL tab and enter the following query:
UPDATE `mdl_role_capabilities`
SET `permission`='1'
WHERE `contextid` = '1'
AND `roleid` = '7';
3. Click on the Go button.
4. Now log into your Moodle installation.
5. Go to Define roles page (Administration > Users > Permissions > Define roles).
6. Select the Authenticated user role.
7. On the View role details page, select the Reset to defaults button, and finally click on Yes.
Though it was no fun setting the 223 capabilities of the authenticated user to Prohibit, it was interesting to see the behavior of the installation, and I could also confirm that this solution works.
Cheers!