The problem I had with mine was that it would check the connection, tell me that it was ok, then try and connect and update. It hung for a few minutes then chucked up an error message.
I read the router faq on nintendo wii website and it suggested changing the wireless channel to 1 or 11 (I think), mines was about midway at 5 or 6. I changed it to channel 1 and it got it no probs, even on auto setup.
Have a read of it if you haven't already and try the wireless channel change.