The issue that I previously wrote about is finally solved. The previously mentioned support thread provides the solution:
http://discussions.info.apple.com/thread.jspa?messageID=12133546&tstart=0
I fixed the problem by creating a new iTunes account. It is suggested to create an account for another country. I created an American iTunes account without attaching a credit card. This is possible from the iPhone, but I did using iTunes on my Mac. For instructions on how to create an account without a credit card check out this link.
How to create an account in another country’s iTunes store is explained here.
When the account is activated you can use this to activate Genius for Apps on the iPhone.
Once activated you can logout again and login using your regular account. The Genius feature will still be available.
I am glad it is fixed. It remains a weird bug though! 
Related posts: