Some users after the WiiConnect update have been having trouble trying to reconnect to the service. If you are getting one of those two error messages try changing your channel on the router to 11 or 1 . Try that before contacting Nintendo and organizing a replacement unit.

For Linksys WRT54G routers enter the ip address of the router (default is 192.168.1.1) enter password and user name (default is admin/admin) then click wireless tab, now select a different wireless channel from the drop down box. Fix is not guaranteed to work for all consoles.

Nintendo Wifi | Nintendo Wifi Setup