The current system for adding pages to a MediaWiki wiki is completely unintuitive. When trying to explain it to people, they get completely confused about why there isn't simply a "create a page" link in the sidebar (or wherever) that can be clicked to start a new page. When I have to explain that you must go through Special:Search or type the title directly into the URL bar or create a link first, people look at me like I'm insane. And in some ways, this model is insane.
MediaWiki needs a functionality similar to that of WordPress where pages can be created by mortals easily. I'm told this might require some reworking of the EditPage.php code, as not having a title already when trying to create a page is currently problematic. That said, I believe this is a very serious user interface issue that should be resolved and it is certainly not impossible to resolve this issue properly.