Proverb: "A new broom sweeps clean"

The tense should remain the same as the definition of a new broom remains constant.

A new broom sweeps clean TFD

Prov. Someone who is new in a particular job will do a very good job at first, to prove how competent he or she is.

As in:

Jill: That new supervisor is awfully strict. Jane: New brooms sweep clean. The new teacher immediately flunked three of the laziest students. "A new broom sweeps clean," one of the students shrugged.

Also note:

You can also use the proverb a new broom sweeps clean. "A new broom doesn't always sweep clean, it just brushes some of the worst dirt under the carpet for a while".

As mentioned you can exercise poetic license and change the tense ... but most proverbs and idioms are used unaltered.

It seems to me that authors may use a proverb such as "A new boom sweeps clean" in either of two fundamentally different ways. One way involves treating the substance of the proverb as an eternal verity. In such a case, the past, present, or future setting in which the proverb appears has no bearing on its currency—and expressing it in present tense, regardless of the time frame of the narrative in which it appears, makes perfect sense. Thus, for example, you might encounter a paragraph such as this one:

Longtime staffers had hoped that the new head of marketing would avoid making drastic changes for a few weeks at least, if only to get a clear idea of how the department had traditionally done its work. But they also knew that a new broom sweeps clean.

The other way involves applying the proverb to a particular case as, in effect, a metaphorical description of specific actual events. In that case, if the events are presented in past tense, it makes sense for the writer or speaker to recast the proverb in past tense as well. For example:

Longtime staffers had hoped that the new head of marketing would avoid making drastic changes for a few weeks at least, if only to get a clear idea of how the department had traditionally done its work. But there was no such grace period. The new broom swept clean.

The print record includes various examples of both treatments of "A new broom sweeps clean." An instance in which the proverb appears in present tense after a series of past-tense constructions occurs in Richard Carlile, A New View of Insanity; in Which Is Set Forth the Present Mismanagement of Public and Private Madhouses, All the Late and Existing Defects of New Bethlem: with Some Suggestions Towards a New Remedy for That Almost-Universal Disorder of the Human Race (1831):

The abuses of Old Bethlem had become a great public nuisance. They were exposed in 1815 ; and a new system was called for, and promised, as to New Bethlem. It began well, upon the principle that a new broom sweeps clean ; but now, unless a check be put upon the again growing abuses of the hospital, it will soon become as bad as it was in Moorfields.

In this case, the present-tense form of the proverb appears after a series of past-tense observations. The paragraph then shifts first to a present and then to a future perspective—but the author's use of present tense for the proverb itself does not rest on those subsequent developments.

Next we have an example in which the author recasts the proverb as a metaphorical statement of an actual specific occurrence. From Charles Lewes, Memoirs of Charles Lee Lewes, Containing Anecdotes, Historical and Biographical, of the English and Scottish Stages, During a Period of Forty Years (1805):

For a long course of years, through carelessness in the players, otr inattention in the manager, Herbert's company was reflected on for the slovenly manner they conducted their rehearsals ; but after repeated animadversions on this want of respect to their friends, the public, they one and all agreed to a laudable regularity in that necessary preparation for the business of the night, and under a considerable penalty to begin their rehearsals every day (Sunday excepted) at the hour of ten, allowing, at the same time, ten minutes grace. This new broom swept clean for some time, and its unremitting severity had pinched the stipends of many of them, both male and female.

The applied form of the proverb in this instance is situation-specific (note the use of "the broom," referring to a particular figurative broom, in place of "a broom," the generalized representational broom of the forever-true proverb): it refers exclusively to the sweeping of money from the pockets of the members of Herbert's company in the form of fines for missing or being late for rehearsals. And because that sweeping occurred in the past, the author frames the metaphorical application of the proverb in past tense.

Finally, let's look at an example that, effectively, uses both forms. From W.S. Bain, "Establishing a Practice Under Difficulties," in The American Medical Journal (July 1886):

There was one old fellow who had the lead of the practice in this country [Caddo Mills, Texas], and whom I shall style as Dr. Mountebank No. 1. Now this Dr. Mountebank No. 1 interrogated a lady that OI had happened to get acquainted with, in a taunting way, and wanted to know if she had seen the new Dr., and if I had received any calls. She answered him by stating that she had met me, but did not think I had received any professional calls. At this news Dr. Mountebank No. 1 laughed heartily, and said some one ought to send for me, as a new broom sweeps clean. (How true his words were verified in his own case, for the new broom swept him out of practice).

The proverb first appears (in present tense, in the midst of an extended past-tense reminiscence) as a statement of eternal verity. Then, in slightly altered form, it appears (in past tense) as a metaphorical representation of what actually occurred at the end of the remembered episode.