I've been having problems making my Wii connect to the Internet. The Wii Shop was working fine, but it failed to download system updates (error code 32004) or Opera (error code 204904).
My specific setup was a wireless connection to a Netgear WG602v2, wired to a Vigor ADSL 2200 USB, using Demon Internet in the UK. I eventually found that the problem was with the DNS settings. Originally it was set to auto-detect all settings through DHCP. After changing the DNS name servers to those used by Demon, firmware updates and Wii Shop downloads started working again.
How to fix: Go to the connection settings. Pick a connection, and enter the manual setup for it. Set up your wireless settings as usual, but when you get to the DNS settings make sure they are set to manual setup. Enter the IP address of your ISP's DNS servers (*not* the address of your router). Set up the rest as usual (if you don't know your MTU, 1492 usually works).