If that's the problem, a dealer would have to either replace it if it's bad, or possibly just re-synchronize it to your keys.
It's not a common issue. I only mentioned it as it would cause the engine to crank without catching as yours is doing, and it seems possible that an electrical device could have been damaged during the battery change (since you got a spark large enough to blow that fuse).