The "nice" thing to do is ask the client if they can get the logo from the old shop. If the shop refuses, then you can sell them a logo redesign and that they get to keep the logo.
If you redraw the logo and that logo has a registered copyright from someone other than the client, then you can be in a world of hurt. If the logo is unregistered, then you may anticipate bad energy from the other shop, a booger flick up to and including a punch in the nose, to a cease and desist letter (and maybe small claims)