You will need to go to the exact place where the license from the GZ company was issued. Although the procedure used by the GZ company is not 100% legit, the license is. Hopefully, you have a copy of the old license, without it, you probably won't get far, as this is how the GZ company makes its money.

FYI for you BJ'ers and SH'ers... many people need companies like the GZ one to achieve a C1E or C1D license. It's nice that those big fancy cities have rules and procedures, but the vast majority of the cities in China do not issue C1E or C1D licenses to foreigners any more.

Cheers!
ChinaV