I also have this problem. I have aMule running on a Linux box acting as a router (so aMule shouldn't be NAT'ed because traffic is to and from the external interface). I have opened up all outgoing traffic (from the router) and allowed 4662 TCP in, 4672 and 4665 UDP in, and even 4661 in. I do not, however, have UPnP enabled and won't either.
When I copy a fresh nodes.dat to the ~/.aMule directory, after a short period I will get Kad (firewalled). I've sometimes caught it saying Kad (ok) for a short period, but for the most part, if I go away for a few hours and check on the status I get Kad (off).
Oh yes, I am using amuled not the GUI. aMule 2.1.3, wxGTK2 v2.6.3, Unicoded, OS: Linux