I'm no BM guru, so I will go to the most obvious possibility first. Is it possible that when you connect the new workstation that you went over your license count? Potentially passing the buck on who can't get access? I would also look at the Access list features of boarder manager and make sure that the IP address bound to the clients is listed as acceptable traffic....is it possible that you created a DHCP scope outside the range of IP addresses allowed to connect to the firewall based on its current config?

-w00kie