This is normal behaviour.
Just export the private key used for signing from machine A and install it under the same user account (or whatever process signs the messages) in the same certificate folder in Machine B.
To access the cirtificate store…
Start -> Run -> MMC
Then add the certificates store.
TM