For some reason the iPhone 3G will not connect to this wireless router. There has been talk that this is fixed in the latest firmware but as of writing this it is not fixed in the latest AU/NZ firmware (1.00.23).
I found a temporary solution for the problem though. If you limit your router to 802.11B only then the iPhone will connect without a problem. As soon as it's changed to mixed network or 802.11G only then it will fail to connect.
Update: I've found that the AU firmware from the AU linksys site works fine on the NZ WAG54Gv3. I'm using 1.00.46 and the iPhone 3G now connects under 802.11G without a problem.