Q: I haven’t been able to get iTunes genius to work for a long time for any of my songs, even the ones I purchased through the iTunes Store. If I buy a song, update genius and try make a genius playlist from it, it doesn’t work. Any ideas?

– Sam
A: Firstly, to be clear the Genius feature does require that you have enough similar music in your library to be able to create a viable playlist. If you’re working with a more obscure track—even if you purchased it from the iTunes Store—it may simply not be possible for iTunes to find enough matching content in your library.
It’s also worth keeping in mind that the same rules apply when working with the Genius feature on an iOS device, except in this case Genius can only choose from the collection of music actually stored on your device, generally providing more limited options than your full iTunes library would.
That said, since you’ve indicated that Genius isn’t working for any of your tracks, the most likely cause is a corrupted Genius database in iTunes. iTunes stores its Genius data in a separate database file, appropriately named iTunes Library Genius.itdb. Since this file is generated entirely by the iTunes Genius setup process, you can actually delete it with impunity and iTunes will simply re-generate it the next time you restart iTunes or run the Update Genius option.
The cleanest way to do this, however, is to turn OFF the Genius feature manually by going to the Store menu and selecting Turn Off Genius. You’ll be shown a dialog explaining the process of turning off the Genius feature and asking for confirmation. Note that any Genius playlists already in your library will be preserved, but will be transformed into normal playlists as part of this process.
Once the Genius feature has been disabled, shut down iTunes and then open a Finder or Explorer window, navigate to your Music/iTunes folder and delete the file named iTunes Library Genius.itdb. You can then simply restart iTunes and turn Genius back on as you normally would and it will rebuild the Genius database from scratch.
Note that the Turn Off Genius option will not appear if you’ve enabled iTunes Match, since these features are dependent upon each other. In this case, you will first need to turn off iTunes Match before you can turn off the Genius feature; turning off iTunes Match merely de-registers your computer—it will not remove anything from your iCloud music library. Once you’ve rebuilt the Genius database, you can simply re-enable iTunes Match as you normally would, which will run through a very quick process of re-registering your machine—since nothing was removed from iCloud, iTunes will not need to re-match or re-upload any content.