It really depends on so many factors that it's hard to answer. For starters, the laws vary from state to state, country to country, etc. Secondly, the situation can vary depending on what the job is. For example, if the employer is in the fields of law enforcement, finance, defense, government, or even transportation there could be special rules or circumstances.
For example, our city school district outsourced a fair number of positions for school bus drivers. The companies contracted to provide the drivers were supposed to perform background checks. Apparently some of them were missed, or were not as thorough as they needed to be, because one of the contracted drivers was arrested on duty for possession of cocaine and at the time it came to light that the driver had previous DUIs and charges for possession of drugs. After that school was cancelled for several days while background checks were performed on ALL of the bus drivers in the district. Some of them were let go as a result.
I'm sure that some of them thought that it was draconian, but I think that most people would say that not only was it fair, but that the school district had a moral imperative and a legal responsibility to do what they did.
One thing that I can say for sure, it is now pretty much standard practice for any professional position to require drug screening, criminal background checks, and in many cases credit checks as well. That being the case, it's probably not illegal (or even unexpected) that a process that performs ongoing background checks would be used.
That being said, in some states or countries it might be illegal to fire someone for something that wasn't strictly related to job performance (once they already had the job). It might also be of questionable legality if background checks were performed only on select individuals (where their jobs didn't require additional security precautions over those applied to a regular employee).
This particular example could also be a case where background checks were not being performed on new hires, but the company wanted to start doing so and felt like they had to also run checks on existing employees in order to cover themselves from a legal standpoint. As long as they're treating everyone the same, there's probably nothing illegal about it.