As an update, I found out how to solve this problem from this thread at the Apple support forums. Well, thank you very much for nothing Apple, since I had to figure out this crap on my own.
It is one of the weirdest bugs I've ever seen, but apparently, if you have multiple keyboard layouts set for your Mac, as I did using the US International layout to be able to type in diacriticals for latin languages, the dialog asking for your admin password would never come up.
This affected everything from program installations to unlocking certain preference panes.
So the only way to solve this was to remove all keyboards but the US one (I don't know if it happens for other keyboard types, since I have a US layout keyboard), and then add the other layouts back again.