Blah!!

[Joker85]

I had this same problem.

Download the Windows Installer Cleanup Utility.

EDIT: Found a link that works:
http://windowsxp.mvps.org/msiclean.htm

Uninstall the game, reinstall it, download the patch (but don't install it), then run the program.

Once you run it remove "Rome - Total War(TM)[1.0]"

and "Rome - Total War(TM)[1.2]"

Install the patch and everything should be good.