I'm not sure if they changed anything, but Youtube has been the first search result for me since I upgraded my iPhone. It's not in the search results for the iPad since Google hasn't released Youtube for the iPad yet (or at least last time I searched).

I wonder if there's saved state in the app store that's modifying the search results.