To me this sounds as if SA is doing some network tests that it simply is timing out in. Is the server behind a firewall or running as FW (server-gateway)?
Try to disable some of the network tests in:
/etc/mail/spamassassin/init.pre
I would suggest to disable SPF, Pyzor, DCC and Razor2 and the see.