There's a huge difference between modifying the exe file itself (including decompiling it, modifying the decompiled source code, and recompiling that, which is what was done with Terraria to make some of these programs), and "mods" which modify other components of games, such as artwork, or removing the startup commercials, which can often by done by simply deleting the movie files for them.
Posting a program that mods another program - I don't think that's illegal, but I'm not 100% certain. The way I understand it, that wouldn't be illegal, but running the program would be, or something like that. It's all a bit confusing. In any case, there are situations where it's legal to modify a program to remove copy protection (generally when the copy protection does not function properly), or to modify programs in general (to make them work on your computer, because they are too old to do so), but it's still illegal to distribute the modified programs. But that's not what we were talking about, really.
We're not talking about works in the real world, we're talking about programs. Programs can be copied. Programs can be modified without destroying the original. Replacing the sprites in data files has nothing to do with modifying the program itself.
[4 new replies have been posted! Do you want to re-- no! I'm leaving now, damnit. :<]