I had one music library that Apple wouldn’t deliver Genius results for. One forum said it was because of screwy characters in the track info. I did examine the XML file, and found a bunch of characters with diacritical marks, but it wasn’t worth the time to try to find and replace them all.
I just installed iTunes 9 on that Mac, and it brought Genius down lickety split.
I’m running home now to get iPhone 3.1 and iTunes 9 on my own machines.