Looks like if I would have read the Apple discussion post a bit longer before hastily writing my last post, I would have found the solution. For anybody that is consistently getting a 4010 error, this seems to work:
(1) Open [username]/Music/iTunes/ in the Finder.
(2) Make a copy of "iTunes Music Library.xml"
(3) Validate the XML file. The easiest way to do this, if you have Firefox 3, is to open the "iTunes Music Library.xml" file in Firefox. Depending on how large the file is, this might take some time. Presumably, at this point, you'll get an error message saying that there was an XML Parsing Error.
(4) Find the song that is causing the problem. If you can't tell which song it is, you may have to open up the file in a text editor, and navigate to the line number specified.
(5) Go into iTunes, find the song, right click it, and click "Get Info".
(6) You should see some funky characters somewhere. At this point, you can either (a) delete the song, or (b) click on Info, and make sure to completely delete and re-write all the information.
(7) Once you've done that, re-load the file into Firefox and correct all the songs until there are no more errors.
(8) When Firefox parses the file correctly, quit iTunes.
(9) Open the [username]/Music/iTunes/ folder in Finder again and remove the "iTunes Library Extras.itdb" and "iTunes Library Genius.itdb" files by dragging them to the Trash and emptying it.
(10) Restart iTunes, enable Genius, and voila!
It's quite unfortunate that iTunes doesn't seem to be able to repair corrupted XML, or at least tell you that that's the problem.