Just an observation - I used to get this message ALL the time. I haven't had this issue after I made upgrades to my router (from 10-year-old Linksys WRT54G to Linksys E3200). The WRT54G didn't have any obvious problems, I just wanted the ability to have Wireless-N for my Apple TV. With the new router in place, I haven't seen the error since. This accounts for old iTunes (older iOS before the 5.1 upgrade came out recently).
Furthermore, my condo has a TON of neighboring WiFi networks (seeing 15-20). I followed all the best practices (i.e., using the least busy 1/6/11 channel, put the old router in a central location), regardless, I wonder if interference was an issue in the past - theory is new router has an improved antenna and handles that better.
I am not necessarily saying you should get a new router, but wondering if interference from a lot of neighboring Wireless networks may be a contributing factor.
Tom