I'd start off simple...
spamassassin --lint -D
See what that can tell you. If that's showing network tests working, try adding -D to spamd's start up (note: spamd not spamc) and check your syslogs. (warning: this will dump lots of debug into your mail log)
Aha!
debug: is Net::DNS::Resolver available? yes
debug: Net::DNS version: 0.45
debug: trying (3) ebay.com...
debug: looking up NS for 'ebay.com'
debug: NS lookup of ebay.com failed horribly => Perhaps your resolv.conf isn't pointing at a valid server?
debug: All NS queries failed => DNS unavailable (set dns_available to override)
debug: is DNS available? 0
However, "dig ebay.com ns" gives me valid results. (I'm running BIND and resolv.conf points at 127.0.0.1.) So it looks like maybe something's wrong with Net::DNS.
Hmm, just retried it twice more, and the test succeeds on these two tests. Perhaps Net::DNS gives up too quickly?
