I'd venture to say it's a network issue. Are the Mac clients and the Windows clients connecting via different methods, i.e. Mac via VPN over modem and Windows via regular non-VPN connection?
Only reason I suggest that is something similar happened to my users. One group had wireless modems over the cellular network another group was connecting from their 'home' systems via their respective ISPs. Security had configured firewall rules to allow the cellular IP subnet, but not the varying 'home' connections. Was a massive PITA until we figured it out.