It's not a problem with the Wii, over here it worked fine as soon as I set the Wii to widescreen. Some TVs detect widescreen automatically, some don't.
As for your connection, it depends on how your network is set up. Do you have a router? Are you also connecting via wireless with your PC? If so, your Wii network settings should match your PC settings. If you're using Windows, go to the network settings, and find the TCP/IP properties. Ask more questions if you need help.
My Mario Kart Wii friend code: 2707-1866-0957