When using menu builder (Appearance > Menus), everything is fine if the pages you're dealing with were created after upgrading or installing WP 3.0.x. If the page was created in WP 2.9.2, the results are mixed, in that a) they don't always show up in the list of available pages, b) they may be in the wrong order, and c) they may or may not come up when using the search feature.
Unfortunately, this requires one to start with like a WP 2.9.2 install, so it may be difficult to re-prove, but
1) while in WP 2.9.x, create a few pages (I have 122 pages, some 2 levels deep - may have something to do with it).
2) do the automatic upgrade to WP 3.0.1.
3) navigate to the menu builder (Appearance > Menus)
4) try finding or searching for the pages. They will be out of order and/or not there and/or not searchable.
5) edit and re-save one or more of the old pages. This MAY make them searchable and/or findable on the list.
6) create a new page ... it should work without any hassle.