Scenario
All users including Administrators cannot create new Knowledge Base due to the permission violation stated above.
Solution
To resolve this, in addition to Knowledge Base feature that needs to be enabled, Intranet feature should be enabled in the account.
1. Login as Administrator
2. Navigate to Setup > Company > Enable Features
3. Click Web Presence subtab
4. Intranet: Mark the Checkbox
5. Click Save