The user docs for confluence 3.4 indicate that users should use the "Web Link" option for adding links to new pages:
http://confluence.atlassian.com/display/DOC/Adding+and+Removing+Links+in+the+Rich+Text+Editor#AddingandRemovingLinksintheRichTextEditor-LinkingtoaNonExistentConfluencePage

This is completely counter-intuitive, as links to new pages would never be web links, especially as the url hints "http://" by default.

I've been using confluence since v.1.4, and this is one of the first times I've been completely stumped (obviously I know how to do this in the wikitext editor).

I suggest either:
a) adding a "Create 'New Page' link to: <page name user typed in> in the auto-suggest drop-down list, perhaps above the entry for "Search for '<page name user typed i>'" (probably the preferable option), or
b) adding a "New Page Link" option on the left of the link editor