We have 2 MCS servers.
I would like to upgrade the Unity server first but want to make sure that it will function properly with our CallManager server. I would be upgrading the Call Manager server a few weeks later. this upgrade is in dier need due to the fact that both versions of Unity and CallManager are at end of life. Our 2003 Exchange server is on its own platform.
Looks like Unity 7x works fine with CUCM 4.1 so you should be ok. Here is the matrix link for version combos.