this is something that was changed on WP 3.3.1 I think, try this go to settings > gallery > general and check “Searchable Galleries”