Your problem is simple.
You need to determine what makes more sense in terms of RDS CAL licensing for your environment. If you have multiple shifts for example, where workers share the same computers (meaning more users than devices) it makes sense to license per device. If users connect from several locations (home, multiple office PCs, laptops, etc meaning more devices than users) you should have per user licenses.
As pointed out these are NOT concurrent.
The other thing to keep in mind is per DEVICE licensing is ENFORCED what means if you run out of licenses you do not connect. Simple as that (you actually get a temporary RDS CAL and after 90 days with no RDS CALs available that one expires and you get screwed).
As a workaround until you get more licenses you can simply delete the registry key HKLM\Software\Microsoft\MS
Licensing on the device that cannot connect and it will get a new temporary RDS CAL good for 90 days.
For more information about licensing please download and read the guide I wrote, "Terminal Services A to Z" available at no cost at
http://www.wtslabs.com. It explains all that and much more.
Cláudio Rodrigues
Microsoft MVP - Remote Desktop Services
Citrix CTP