Maybe I can give a little more info about this. I'm using the cvs version of amule in a debian testing machine.  There is no NAT, no filter, no port forwarding. I have a direct cable connection, and my box is directly connected to the internet. iptables rules are per default set to accept.
ii  amule-cmd                           2.1.3+CVS20071029-1                 the amule-commandline-client
ii  amule-daemon                        2.1.3+CVS20071029-1                 the amule daemon
ii  amule-i18n-en-gb                    2.1.3+CVS20071029-1                 English (en_GB) internationalized (i18n) fil
After seeing this in the logfile:
2007-10-30 10:10:51: Disconnected from Kad
2007-10-30 10:10:51: Indexed.cpp(249): Kademlia Indexing: CInvalidPacket Exception in CIndexed::readFile: CInvalidPacket: Integer
tag expected, but found "^B"=Type=10
2007-10-30 10:10:51: RoutingZone.cpp(150): Read 182 Kad contacts
i did a status:
$ status
 > ED2K: Connected to xxx[xxxx:5000]  with HighID
 > Kad: Not connected
 > Download:    43.65 kB/s
 > Upload:      9.74 kB/s
 > Clients in queue:    1737
 > Total sources:       1928
not connected!, then, connect manually
aMulecmd$ connect kad
2007-10-30 11:10:51: Kad started.
couple of tries an minutes after:
aMulecmd$ status
 > ED2K: Connected to xxx[xxxx:5000] with HighID
 > Kad: Not connected
 > Download:    43.75 kB/s
 > Upload:      9.45 kB/s
 > Clients in queue:    1733
 > Total sources:       1936