Two weeks later, the authorities sent me a new card with the same number, but without any employment restrictions. Michael also went through the same process, as his card had the clause "Valid for work only with INS-Authorization" under visa status. With a Green Card, he is now free as well, as he can work for any employer without the need for approval from the immigration authorities.
Furthermore, I filled out the I-9 "Employment Eligibility Verification" form, which every American employer must have on file for both American citizens and "everyone else." Essentially, you are certifying that you are indeed eligible to work and that you are who you claim to be. However, a signed certification alone is not sufficient; the employer is required to review the appropriate documents, such as a driver's license with a photo or a passport, as well as a green card and social security card.
And because I work with children, the state of California continues to require that my fingerprints be taken to check that I don't have any prior convictions related to child abuse.