First of all I'm not sure you need to do
.WithAllData to take a count - if I'm not mistaken it joins coupled table, which is not needed in this particular case.
Does user account, that macro was signed by in source env, exists in destination env?
Public user definitely is not a good option to sign macro with - you need to sign it by a user that has appropriate permissions.
First think I'd try is removing the signature and saving the macro again in destination env, so system signs it once again and it seems you've already tried it.
Next thing I'd try to completely remove macro and type it in again in destination env.