This bug was reported earlier this week. It's slightly surprising to me because it's a fairly serious bug and the code that causes it has been present in the product for over a month, yet it took this long for everyone to start notice it was happening.
What happens is that the existing code that checks if users are allowed to edit titles also considers whether they are a moderator or not. So even if they "Can edit titles," if they aren't a moderator, then they won't be able to. When creating a new article, VaultWiki doesn't distinguish it from an edit when preparing the title field and ignores the value, essentially making it NULL. With the title blank, VaultWiki redirects to the Search page.
For the next build (shortly today), fixed both the overprotective title edit permissions and not being able to successfully create without them.