You probably have been asked for documentation that gives you permission to work. The Department of Labor has a list somewhere (can't find it right now) of what constitutes a work permit, and the employer has to accept anything that conforms.

My wife ran into a particularly obstinate HR drone once who wouldn't accept what she had. She asked company counsel if her documentation was in order and received a phonecall from HR to please come in and sign paperwork before the day was over. Yes, federal law has teeth.