The most common way to setup a network when using a Linksys router is not to make any settings at all, just do DHCP to the router and let it make the assignments. One down side to this is that it may be hard to lock particular local IP addresses to particular computers, and this makes port forwarding for servers a pain. But if that's not an issue I would certainly try to go with DHCP.

I'm mystified as to where the 172.16 addresses are coming from. This is a private unroutable range, so it can't have anything to do with your ISP's real DNS servers. I'm not even clear if it's coming from your router or from something else. I don't really expect that it is coming from the router, but I would do the following: Enter the router setup and see what DNS servers it says it is using; confirm they are real routable addresses. Consider using them instead of the router's 192.168.x.1 address. Check if there is a newer version of firmware for that router. If not, at least reset the router and see if that helps. Or if you have an alternate router that you could try, use it temporarly and determine if the router is a factor at all.

I'm not really concerned about the type of Knoppix install you did. I've seen enough reports of strange problems after any type of Knoppix install (except perhaps the "poor man's install"), and particularly networking problems, that I have come to believe it's always a questionable idea. I have never had a problem like this into any of my routers with real Debian installs.