Apple Support Discussions user "Jon August" reports:
For the last few days, I've been trying to get a Genius Update on a song I purchased. Specifically, "Lions" by "The Features". Every time, it comes back with:"Could not complete the iTunes Store request. The store may be busy."There's nothing wrong with my internet connection.
Other users report similar problems with different songs over the course of the next couple days. One user did report that they were able to finally get the syncing to work after repeatedly trying for about an hour, though no other users commented about that strategy working for them. Some users have gone as far as toggling Genius mixes, reinstalling iTunes, restarting their Mac, changing DNS and firewall settings, all to no avail. This issue appears to be on the Apple side of things, likely a bug inside the iTunes Store servers. There has been no official statement from Apple regarding this issue as of this posting.