[SOLVED] (And I feel dumb, because it was kind of obvious)
Still, more details:
The issue happened on a local development machine. Accessing the wiki via "http://localhost", and then logging in, worked fine. However, accessing it through a domain name "http://wiki.mydomain.com", mapped to the local machine via /etc/hosts did not work. Using the same login information, the error "Permission Denied. Sorry, you don't have enough rights to continue." appeared after submitting the login data.
The issue was HTTPS. Because modern browsers do not store cookies of insecure domains anymore, the user session was never saved by the browser. I've set up my local domain using HTTPS, and everything works fine now.