You running any domain or extra functionality on SBS or just email, I mean that shouldn't influence the Linux LiveCDs you've tried but still worth a look?
From what you've said I'm inclined to believe the common element is the router, unless a common configuration has been applied to each computer but the LiveCDs have eliminated that. Check the DMZ as I've said below just to make sure nothings in it
I'd try a complete reset of the router just to eliminate anything at that end, if you've got a spare try that. Failing that go to the firewall and turn off options to test (start with the more esoteric) check to make sure nothings in the DMZ, Access restrictions are usually done for each individual device from the LAN tab so its odd that it would be turned on for all but worth a check.
I mean has it always been like this, have you recently moved sites, has a former employee just left?
This is a complete non-sequitor but if the recent testing has been all from the usual windows machines its worth a try from the command line do a
netsh winsock reset
netsh int ip reset all
and then restart, I don't suspect it will work but like I said worth a try. Another option and I'm really going out on one here is to monitor the connection with something like http://www.wireshark.org
