What is going on is this:
To remain in the US on a student visa, you need to be "in status". The government has rules on what that is, and mostly it is that you continue to register for a full load. I do not think the government has specified additional requirements.
However, each university has an international programs office and they are required to specify for each international student whether the person is compliant with the university's guidelines. In your university's case, that office may have decided that "Hey, if you're a PhD student, you can't go too long without an advisor, because that would mean you're not making progress towards a PhD." I've seen them say similar things if it's taking too long to get a degree (e.g. over 6 years for undergrad or 8 years for PhD). Or if the GPA is too low and you're on probation
Typically, these rules apply to all students, and not just international ones. It's essentially the university saying "You're about to be kicked out/expelled, so we can't tell the immigration folks that you are progressing towards your degree"
Still, I really doubt your university has a rule specifying only 30-60 days to find a new PhD advisor. To give you an idea, in many sciences, it's common that you don't have a thesis advisor until after your first year (you focus in the first year on passing your qualifying exams, and only once you pass it are professors interested in taking you on).
If indeed your university is enforcing a 30-60 day rule, it's a really crappy university.
TLDR: The law doesn't require it, but each university has its own policies.