iPod Touch won't connect wirelessly to iTunes (Remote App)

I've done my testing on two computers.
One is an Intel iMac with 10.4.11
the other is an Intel iMac with 10.5.4

On both computers, internet sharing is enabled.
The wired connection is shared through the wireless connection.
(So the iPod touch and iPhone can connect to the wireless, and use the wired connection)
The connection is secure (Enable Encryption is checked), with 40-bit key length.
The firewall has been set to allow all connections.

Both computers have the iTunes Preferences -> Devices set to
"Look for iPhone and iPod Touch Remotes"

I also have an iPod touch (with 2.2 firmware)
and an iPhone (with 2.1 firmware)

iTunes is version 8.0.2 on both computers.

The iPod touch and iPhone both connect wirelessly to each computer.
(Opening Safari and browsing the web to check connectivity)

The iPod and iPhone both have the same version of the Remote app from the app store.

When iTunes is open on the 10.4.11 computer,
and the Remote app is open on the iPod touch and iPhone,
both will show up under Devices, and allow it to control iTunes.

When iTunes is open on the 10.5.4 computer
and the Remote app is open on the iPod touch and iPhone,
neither the iPod or iPhone will show up under Devices.

Unless 10.5.4 handles Internet Sharing differently, it shouldn't be an IP conflict since they connected on the 10.4.11 computer.

I've already tried reinstalling iTunes on the 10.5.4 computer.

But neither iPod or iPhone (connecting wirelessly and using Remote app) will show up under Devices in iTunes 8.0.2 on a 10.5.4 iMac.

Any ideas?