I don't know if this situation applies to you, but you have to make sure that the iTouch and your instance of iTunes are talking to each other on the same IP subnet.
It appears that Remote is scanning only the network that the iTouch is registered to for instances of iTunes. Once I put both devices on the same network together, they popped right up.
Also, I tried variations of launching iTunes or Remote first, I think I was successful when iTunes launched after Remote was already running.