Not many people here are familiar with Canadian/US systems, but I'll hazard a few guesses.
Was the MO in $CAN? If so, the store in the US would have to pay a fee to bank it - $75 sounds a lot though. If it was in $US there shouldn't have been a problem.
If you get it back and take it to the PO you bought it from (with receipt/counterfoil or whatever they do) you should be able to get your money back, but probably not the fee you paid to buy it.
I'm surprised that ANY countries ouside Canada take $CAN money orders without a fee. An IMO expressed in the currency of the destination country, no problem, but $CAN is going to cost everywhere. Maybe they didn't know what they were doing and got hit with the fee later.