The first thing I would add is a middle name optional field. If you search "Levi S" you will get any 'S'. I usually just drop the middle initial to get better results.
The locations should be able include and exclude by category. USA includes Illinois includes Cook County includes Chicago. This would make it easier to use and understand.
But my biggest issue is with the wildcards. You guys have to figure out a way to get over the hurdle of three letters before a * is used. In your example, the best way to search would be for first name, exact, L*, last name exact Baker. This would include all the L, Levi, Levy, Lou and Louis and anyone else starting with an L out there.
I did notice that some things have been tightened up. Over the last week I kept getting 1000+ hits in some Minnesota mining database that I don't see now.
One last thought. The old and new searches do NOT return the same results, which is a huge problem. Here's an example: Search for an exact match for Margaret McElrath and take a look at 'Newspapers & Periodicals'. New search returns 9 results. Old search returns 10. The one missing in the new search is "Historical Newspapers, Birth, Marriage, & Death Announcements, 1851-2003" which has an obituary from The Atlanta Constitution. The exact record I was looking for! Had I not gotten completely frustrated with the new search I would never have found this. I think more continuity testing is in order and a lot of 'stare and compare' on behalf of your QA team.
All in all, I do prefer the new search. I can't wait for it to get better, though.
I really hope they get this new search working, because it is so much better than the old one.