You are correct about Gnutella being uncentralized, so let me see if I can clear something up for you...
The "Server Busy" you see is refering to the user you're trying to download from. For example, if the guy you want your file from only allows 4 downloads at a time, and you're person #5 to want to connect, you'll have to wait your turn.

Each and every Gnutella "client" on the network is it's own server. They all perform 3 basic functions:
1-To host files available for download
2-To accept and relay search requests from other servers
3-To allow you to download files from other servers

I got a little trick with MPE to get a good sized library of available files...
If you're on dial-up, set your minimum connections to 4 and max to 5, and set it to drop nodes with less than 200 friends.
If you're on Cable or DSL, you can have a much higher maximum of connected nodes. I'm on cable, and have mine set for a minimum of 18 and a max of 20; I can usually get a Library of around 10TB out of that!

Basically, it's beauty versus guarentee... you can have the beauty of a propriety network such as KaZaA, or the guarentee that you'll still be able to connect when servers fail on Gnutella.

As for your question with Gnucleus, I tried it, and got rid of it when I found I couldn't monitor Library size... so I can't answer you there.

Hope that helps