When I worked with work permits 3 years ago, it was your employer who had to apply for the work permit not the individual. Therefore, your new employer should be willing to do the paoerwork and request for a transfer of the permit to their name (change of employer). Things have changed since. So if I were you, I would check with the Arbeitsamt. There are some very nice helpful people there.