Webster 1913 chimes in with only one relevant meaning of the term:
Mode or system of rule or management; character of government, or of the prevailing social system.
From this alone it seems clear to me that regime change is no where near as precise or technical a term as has been implied elsewhere on this node. If one digs deeper into the meaning of "regime" this point becomes even clearer. The American Heritage Dictionary of the English Language, Fourth Edition, 2000, http://dictionary.reference.com/search?q=regime (Accessed Jan. 3, 2004) states (usage examples are in italics):
a. A form of government: a fascist regime
b. A government in power; administration: suffered under the new regime.

2. A prevailing social system or pattern.
So a mere change in occupancy of the Oval Office constitutes a regime change under the second most common use of the term regime. Or, a regime can change without a change of leadership, because it changes character, mores, or mode; it certainly doesn't require the legal system to be overthrown. For example, FDR's "New Deal", with its shift of power from Conservatives to Progressives, from Republicans to Democrats, from the "old guard" to the "Brain Trust", and from "rugged individualism" to the progressive welfare state, represented a distinct, yet hardly illegal, regime change. True, some will argue that elements of the New Deal were unconstitutional, but the scope of change was so dramatic and deep (indeed, it was as much a change in outlook as it was a change in power or policy), that the New Deal would still have been a regime change had elements of the New Deal been repealed on Constitutional grounds. One could even argue that FDR's switch from bi-partisan isolationism to bi-partisan internationalism, and the formal entry into WW II, was a regime change without a even so much as a change in leadership.

To me, deciding if it's fair or useful to call something a "regime change" has more to do with whether the change stands out as a break with the status quo, and not whether the break was legal or illegal. Of course, often such breaks with the status quo are illegal, since the law is by its nature conservative (note the lower case "C"). It is perhaps even more useful (and interesting), to call such breaks "extra-legal" in the sense that they change or transcend the existing legal paradigm, rather than merely violate it.

The view that "A regime change, then, is an illegal modification of these rules. It is illegal only because if it were a legal change the original regime would still be in place." probably needs to be revised because it is too narrow.