I have iTunes 9.0.1 running under OS X 10.6.1 on two computers - A Mac Pro and a Mac Mini.

On the Mac-Pro, I get the expected behavior when i search directly in song lists.  

> Click on Music under LIBRARY

> Select All (Genres) All (Artists) All (Albums) in the iTunes 8 style top browser

> Click on the 'Name column' to sort songs alphabetically

> Then start typing, for instance "Hall", iTunes jumps directly to the first song that starts with 'Hall', in my case "Halleluja' by Charlie Parker.

On the Mac-Mini when I replicate the above, nothing happens. It looks like the Mac does not respond at all to my typing.  Searching the song using the search pane top-right works both on the Mac-Pro and the Mac Mini