I've been testing the wi-fi device linking with a new CenturyLink 802.11n router, an Apple 802.11g router, an older Apple 802.11b router, and the Internet Sharing function on a Mac. I tested all of these with and without an Internet connection.
All these routers worked as expected when they had an Internet connection, finding other devices in about 10 seconds on the first attempt, and in less than a second after the first attempt due to caching the device addresses. However, I found that the Select a Device window runs very slowly in the iOS version if the router doesn't have an Internet connection -- so slowly that you might think the app has crashed or is not doing anything. (I also found that Internet Sharing doesn't work on a Mac that has no Internet connection.)
In iOS app version 4.1.2, which I submitted to Apple tonight, the speed of the Select a Device window should be back to normal if the router has no Internet connection.
I also added the device IP address to the Help > Troubleshooting page. You can use this to make sure your device is getting a valid IP address from the router, and to find out how high in the IP address range your device is.