All login attempts or ssh login attempts (local or otherwise) ?
You didn't accidentally install the winbind stuff did you when you were installing Samba ? That may have messed with PAM so it is now looking for a Domain that doesn't exist or something ?
Otherwise another common reason for slow ssh logins is if sshd is failing to resolve reverse dns queries.
if 'UseDNS no' in your sshd config speeds things up then this is the problem. Although the cause is that your DNS setup is broken.