After struggling with this error for days, and trying everything I could think of with my routers, I finally came across the answer that you should try first.
Apparently, the WII, and several other things like ssh connections use your network time for authentication protocols. So, make sure your router is set to the correct time zone, and time.
When I updated mine it didn’t initially update, so I updated it to a different time zone five hours ahead of my own, then back and it was perfect. We then played for hours.