Hey - this is proving to be quite a challenge isn't it?! Ok - before you approach your ISP, I think we should try a couple more things here.
Let's take the router out of the equation totally - can you plug your broadband modem directly into your PC ( presumably via USB or ethernet port ) and see if you get any joy? Remember my warning above about ensuring your PC's firewall etc are enabled!
Another thing to check is to see if your PC is using a local hosts table - open up the following file in notepad -> "c:\windows\system32\drivers\etc\hosts", the only things in this file should be a load of comments, plus one hostname definition for local loopback, which should read -> "127.0.0.1 localhost loopback". If you find there are more hostnames in there, then take a copy of this file for safekeeping ( just in case! ) and remove all lines from it apart from the loopback definition.
If hosting works without your router, then I would be pretty certain the problem is with your router config or perhaps is a bug with the router firmware.
Check to see if you have any static routes coded on the router that you are unaware of that is affecting outbound traffic for Warcraft. This is unlikely ( as you would have had to put these routes in yourself ) but still possible.
Another possibility is that you might need to upgrade the router's firmware. Go to the linksys website for the latest firmware downloads ( make sure you download the correct firmware for your county and router version ).
If it's still a no-go with the modem directly connected to your PC, and you are *sure* that the game config is correct plus your PC's firewall trusts the Warcraft application in order for it to allow it to use the TCP/IP stack, then perhaps it's worth a quick call to your ISP's support team and explain that you are unable to host Warcraft III online games - ask them if they block certain types of inbound TCP traffic ( in this case TCP port 6112 ), tell them in detail what things we have gone through here.
Let us know how you get on.