All Unix systems have at least 16-bit user IDs, which can take values from 0 (reserved for root) to 65535 (reserved as an invalid value). Many modern flavors (including Linux) support larger values, but in a mixed network, you should avoid these unless you're sure that all operating systems, filesystems and network protocols support them (e.g. older versions of NFS didn't). There's a general convention in the Unix world that “small” values are for the system and “large” values are for the administrator. “Small” and “large” are not defined precisely; the threshold is typically 100, 1000, or somewhere in between. Furthermore 65534 is by convention the user
nobody, who doesn't own any file and doesn't run any system service (it's used for tasks that should not have any privileges, such as
locate implementations that only index world-accessible files).
The upshot is that any value between 1000 and 65533 is safe. This goes for group IDs as well.
In networks, it's common to use a low part of this range for machine-specific accounts, and a high part for network-wide accounts. If several authorities create user accounts, they may use different ranges, e.g. 10000–19999 and 20000–29999. In your case, it's fine to decide that, say, the range 1000–2999 is for the legacy system and 3000–4999 is for the new system. Or that 1000–9999 is for the legacy system and 10000–19999 for the new system.