First of all, make sure that you have the latest version of your Gnutella client, as an important hostcache (clip2) went offline recently and this has affected some Gnet programs.
Then if you ever get no hosts, type another hostcache into the manual connect bar (most clients have this).
Here's some of the most popular ones:

connect1.bearshare.net
connect2.bearshare.net
connect3.bearshare.net
router.limewire.com
connect1.gnutellanet.com
connect2.gnutellanet.com
connect3.gnutellanet.com
connect4.gnutellanet.com
gnutella.hostscache.com

And I also swear by:

gnutella.hostscache.com

Good luck!

- Tommmo