I finally got my Wii to connect to my wireless network, it definitely took me some time. The error messages that I used to get when I tried to connect earlier, really did not make any sense and none of the instructions/suggestions provided at various forums/Nintendo’s help pages worked.
I have Apple Airport Express (With WPA2 encryption, compatible with WPA and WPA2 clients and using a password) and was wondering if that was the problem. Maybe it was, but if you are having issues connecting your Wii to your wireless network, then also go through the step of manually adding Dns Severs, Ip address, Gateway Address and Subnet Mask in the advanced configuration of Wii Network Setup. This worked for me and hopefully is helpful for someone having trouble connecting their Wii to their home wireless network. I should have worked this out sooner than the time it took me, but, the error messages and corresponding solutions made no sense and in my case were wrong! Thanks for the confusion Nintendo!