I am assuming that your check was returned unpaid to the payee. If so, your quickest rememdy may be to simply issue a new check drawn on your new bank. If they are attempting to charge fees or take collection action against you, I'd suggest providing them with a copy of the correspondence you received from your new bank indicating that your older checks would no longer be honored.
_________________________
It's hard for an egg to become a bird. It's harder for an egg to learn to fly. C.S. Lewis