To be certain, I contacted Microsoft licensing to address your question. According to MS, you do need 2 sets of CAL in general.
There are several types of CAL: per Seat, per Server, per Processor & per Mailbox. Your licensing need depends on the type of CAL already installed. Since you has CALs for another Windows 2003 server, you may or may not need additional CALs for the new server. Please refer to the following link for more information: Microsoft CAL Guide.
There are two licensing models that will affect you – per Device or per User. Consider your environment, if each user tends to have multiple devices (or will be accessing webmail offsite), then User CAL is typically best for you. However; if you are in an environment where you have multiple users to each device than Device CAL would be the better fit. Once that has been determined you can now decide how many CALs you need.
For this example I am assuming you decide on User CALs. You will need a User CAL for Windows 2003 (chances are, you already own these if there are other Windows 2003 servers in your environment as you do not need a new one for every server, it is based on user). Then you need a CAL for any other Microsoft server software running on that server and used by that user. So you would need an Exchange 2007 CAL for each user (you will not find any situation where your Exchange CALs would ever exceed your Windows CALs).
Please note, there is additional functionality in Exchange 2007 that might require an additional CAL known as an Enterprise CAL. You can find clarification on when you need an eCAL through the following Microsoft Licensing Brief (Base and Additive CALs).