I had the same exact problem, playing Zelda US, switching to play Mario & Luigi, and when I got back to Zelda I lost my saved game...
So the problem does not come from using a patched game, but I think more it's a DS-X only problem.
My firmware is the 1.1.2 I think. Well it's the latest one...
I can try doing the process another time with an older firmware, but I am afraid that downgrading the firmware voids the warranty of the DS-X ???
And how can I do the downgrade ? The DS-X team surely does not support this kind of feature.
This is an old workaround I've been suggesting since Pokemon Ranger release. Not sure whether it still will work with Zelda (I don't bother to mess with the DS-X anymore), but it won't harm to try. After playing the other game (Mario & Luigi in your example) and BEFORE executing Zelda again, backup your Zelda save and uncompress it, then try to load the game using the uncompressed save. Of course you must start a new Zelda game to try this workaround, because your current save is probably blank.