[I have let the program run several hours without a single successful connection. Is this normal?]

No, this is surely not normal. I am usually fully connected within app. five minutes.

[Should I let it run for days/weeks to find a host.]

No, certainly not.
First thing you can do ist to manually enter one of the gnutella caches like... ahem... forgotten. Do a web search on gnutella cache, you will find plenty. You can also look at zeropaid.com, eg.
Second thing, and more common, would be a misconfigured firewall. Maybe we could help with more information, then.

Greetings...