FYI, the following site has some decent insight into debugging your Wii network connection - this page is specifically for the indicted error:
Tony, I noticed at the bottom they specifically cover a dynamic gateway/IP issue with the speedtouch.
FWIW, I've tested our Wii on our Dlink wireless router with and without WEP and it connects fine (at least out through the shop/news/weather - no browser at this point). That's also running through a pretty stout SonicWall Pro firewall (more enterprise class) with no problems.
I would have added to the thread (I've been doing networking for years) but RonJon's excellent posts and the above link seems to cover ~99% of the issues!