There are one or two discussions going on at the Apple Discussions boards about users being unable to properly update Genius in iTunes 9, which apparently prevents Genius Mixes from kicking in. Or something. Some posters have gotten fruitful results after eliminating any dead tracks with Super Remove Dead Tracks.
Download and install the script. Turn Genius off. Run the script. Turn Genius back on.