I don’t have any specific solution… but just know you are not alone.
This problem with the Google Incoming Links widget is far reaching, indeed. There are plenty of threads around the web pertaining to the same issue. Bottom line… it has something to do with Google thinking the IP of your install is part of a network with an inappropriately “high” amount of traffic.
I don’t know if it’s shared hosts, or shared domains, or what. I submitted a trac ticket to wordpress… but their only solution was to word the errors differently in upcoming versions?!
Regarding your RSS feed… I’ll take a quick look.