How does Time Machine make room for new users?
My experience is that TimeMachine does not cross the "per-machine" boundary when deleting old backups. 

We have a disk attached to an AirportExtreme AC and which is the target for four Macs. These machines have significant differences in the size of their backups. One of them in particular is an old Mini running 10.6.8 that does not see much activity other than the occasional software update, so the incremental backups are rather tiny. The MacBook Pros on the other hand are a lot more active and regularly submit incrementals that are several GB in size.

Whenever the MacBook Pros need space TM just discards their own history, never touching the others' directories.

This fact is immediately evident when comparing the number of backups for each machine. The Mini has a long history saved, the MBP's quite shorter ones.
Hope it helps.