Custom Menus: add by search doesn't work at all?

Has anyone else noticed that this little search box on the custom menus page (which is supposed to allow you to search for a page to add to your menu) completely and utterly doesn’t work? Am i doing something wrong? I am typing in names that i know exist, but the search doesn’t get them.

I would love any ideas, as I have 500 pages, and the little tiny box is making it really hard for me to make my menu!