Oh sorry, I think my response was presumptuous you were an iTunes Match subscriber. Oops.

Rebuilding your library might be a good idea as a last case scenario, doing so is essentially starting over from scratch, meaning you lose all metadata like heart/star ratings, play counts, playlists etc, but there may be less extreme measures to test out first.
If you are only having problems with Genius, the first thing I would suggest is to quit iTunes, drag the file
iTunes Library Genius.itdb found in your music folder to the trash and re-launch iTunes. This simply deletes a potentially corrupt genius file. When you launch iTunes, Genius should automatically start updating.
If that fails, I would suggest de-authorizing your computer, logging out of your Apple ID in iTunes (which would also effectively turn off Genius) and in iTunes preferences, resetting store cache/preferences.
Quit iTunes and once again try deleting that Genius file
Relaunch iTunes
Login again with your Apple ID & reauthorize your computer
Then update/turn on Genius
Hopefully that works.
As a final note, yes, Genius is broken for recent music but it still works well imo for older stuff. The issue with more recent music has been addressed on here and other forums and many users have given voice to the issue by giving Apple feedback. If you have the time, you can send it here.
http://www.apple.com/feedback/itunesapp.html
It is more impactful when they hear from a plurality of people on the matter.