I suggest that the "ask a question" title box be added to nearly every page of Stackoverflow. When a user enters the question title, it goes to the normal ask a question page with the expanded list of related questions so it acts as both a search box, and a quick way to get started with a new question.
Above the fold screen realestate is 'expensive', and I understand this is a rather significant change for SO. It doesn't fix a 'problem' so much as enhances the user experience of the site. The "Ask Question" button is hidden off to the side, and to new users the presentation downplays the role of asking questions, and instead suggests to them that they should answer questions - the "add a new answer" box is on every single question page.
While the 'old timers' may well bristle at the thought of helping newbies create new questions, many of which are truly sub-par, the whole point of the site is to become a universal programming resource. Having more users with more questions, and capturing more of the worldwide programming audience is more important than maintaining the status quo. Keeping the bar high for new users to almost intentionally limit their interaction with the site is counterproductive given StackOverflow's ambitious goals.
Keep in mind that a lot of people are coming from Google, and they are used to the interface paradigm where the search box is everpresent at the top of the page. If they don't get the results they are after, they merely tweak the search box and press enter.
Rather than forcing users to go back to the google search they came from - and possibly to a different website - it would be nice to capture them in Stackoverflow, and give them what they need here. Present a 'search/new question' title box at the top of every page and let them find the better results here while also suggesting that they can fill out more details in the body of the questions and get nearly instant feedback from the userbase with either answers, or links to duplicate questions.
In order to help them understand that they are best served by staying here, we might also include a small type line right below the question box - "New questions typically receive their first response within 5 minutes. Ask now!"