Linux to Wireless Router - Client Hostname Problem

I have a Linksys BEFW11S4 router that gets "confused" when I boot a
wireless networked Linux system (Mandrake 10.0) up and connect to it.
I lose connectivity to certain web sites from all computers, but can
still get to all local nodes.

When this happens, the DHCP Client Table in the router looks like this
(I munged the MAC addresses for security, they show up okay for me):

DHCP Active IP Table
DHCP Server IP Address: 192.168.1.1
Client Hostname IP Address MAC Address Interface
192.168.1.100 ??-??-??-??-??-?? Wireless
¸#Ð,,ª 192.168.1.102 ??-??-??-??-??-?? Wireless

Notice that the Client Hostnames are not right. If I restart the
router I regain connectivity to the web sites that were not available
before.

Since this only happens when I bring the wireless Linux system onto the
network (the rest of the systems are Windows 98 and XP) I'm guessing I
have something misconfigured there, but don't know what it might be.

Any help to end the frustration will be most appreciated.