Thanks to the power of the internet (and the people on it) I finally got my itunes Genius to work. Here’s what solved my problem:
Download Validator and run it on your “iTunes Music Library.xml” file in the iTunes folder. It tells you where the parser fails. Mine failed with weird characters in a few tracks. Validator tells you the line number but doesn’t let you look at the file, so you go to that line with an editor and find out which track is causing the problem, and fix it. I just had to edit the tags within iTunes.
After that I deleted the *.itdb files and turned Genius on again so Genius would re-scan from scratch, and then it worked! A happy ending.
If that didn’t work there’s a few other things you can try in the Apple Discussions.