You can get by with 40 Windows Server 2003 user CALs. A Windows Server 2008 user CAL permits a single distinct person to use any number of devices to access all the Windows Server 2008 computers in the organization.
Some good FAQs for W2K8 are at: http://www.microsoft.com/windowsserver2008/en/us/licensing-faq.aspx#cals
More info is at: http://www.microsoft.com/windowsserver2008/en/us/client-licensing.aspx
In my opinion, Microsoft makes it purposefully difficult to license their products. (I don't understand why, but that's what it sure feels like.)
Interestingly, the 1st FAQ I posted makes an assertion that CALs are needed for devices that are clients of the DHCP server. I'd never heard that one before. I daresay many compaies are using Windows Server to provide DHCP to devices like printers, wireless access points, and other embedded devices that have never been accounted as "Windows clients" before. Sounds like a great reason to start using ISC DHCPd on Linux to me.