Those files being changed shouldn't make any difference to starting the campaign. So it has to be something else. Is this a correct indication of the things you've tried so far? You should try the rest of them, starting with the -ne and -nm switches probably, as these are quick and easy to test.

X Using a nocd crack? Your game won't work, use the original executable instead. There is no point in trying the rest of the list until you install a fresh, clean 1.5 RTW.
X Install RTW and EB once again, from scratch
_ Add -nm to the shortcut. This disables movies. Using an NVidia 8xxx graphics card? No movies for you, you will probably HAVE to add this switch.
_ Add -ne to the shortcut (and in combination with -nm too). This makes the game windowed. No idea why this would work, but in one case it did.
_ Delete some interfering files that Vista hides in its bowels. These are reported to be in C:\Users\<your username>\AppData\Local\VirtualStore\Program Files\Activision\Rome - Totalwar, at least in one instance where it helped.
X For Vista users, install RTW and EB in a folder outside of "program files". This means changing the default location! You can also try to simply move the RTW installation, but you may be missing some files, so installation is the safest bet.
X Run the validation tool to diagnose the problem
_ Install the fixes linked in my sig.
_ Add more swap space in Windows, and other technical measures you can take
X Using RTW Gold, or an installation otherwise including Barbarian Invasion or Alexander? Try to uninstall everything and install RTW without BI and Alex (remember to patch it to 1.5 if installing from the non-gold RTW disc set).
_ Got an ATI Radeon X700 graphics card? Apparently some setting called "Support DXT textures format" is creating problems. Try to change this setting for the driver called "Support DXT textures format". Try it if you've got any ATI card, really.
_ Try to upgrade your graphics drivers. If it still doesn't work, try to downgrade them.
_ For ATI graphics cards: I'm currently using 6-10_xp-2k_dd_36790.exe as my driver, and have no problems. Downgrading to this has helped at least one other person to get EB to work.
_ Using Nero Burning ROM? Apparently it does something weird to TGA files that causes CTDs when starting EB. At least three forum members got EB to work after uninstalling Nero.
X Check that vanilla RTW works (before or after installing EB). If it doesn't, your problem is not with EB.
X Validation tool says that you are missing patch_1.pak (or something similar)? Get this file and extract it in <RTW>/data/packs.
_ Try to copy the settings found here into both <RTW>/EB/preferences/player.txt and <RTW>/EB/preferences/preferences.txt.