Enterprise was retitled Star Trek: Enterprise at the start of its thrid season (apparently, the Powers That Be wanted to de-emphasize the franchise name for some reason, then changed their minds).
Star Trek Enterprise was originally just Enterprise;
The studio back pedalled when ratings took a plunge and they realised they had to plunder the Star Trek name and image.
Toma became Baretta when Tony Musante refused to come back for the second season and his replacement, Robert Blake, refused to keep the original name.
The Aquanauts – a Sea Hunt clone from 1960, changed its name to Malibu Run (after one of their leads left due to health problems) in February.
Temperatures Rising (1971-73) was overhauled for its second season and renamed The New Temperatures Rising.
Duet moved their characters into a new situation and was renamed Open House in 1989.
The Gale Storm Show was shown in syndication as Oh, Susanna!.
Nichols was renamed James Garner as Nichols in an failed attempt to boost ratings.
Similarly, Dragnet was syndicated as Badge 714.
Oh, and The Seinfeld Chronicles was used as a title for the original four-episode summer run of the show; when it was brought back, it was just Seinfeld
The Andy Griffith Show became Mayberry RFD after Andy Griffith left the show. That’s when it stopped being good. 
The Night Stalker was renamed Kolchak: The Night Stalker.
“8 Simple Rules… for Dating My Teenage Daughter” became “8 Simple Rules” after John Ritter died.
Aaaaccckk! Sorry…wife, wife!
Did Third Rock from the Sun officially become Third Rock, or was it just abbreviated that way on NBC’s ads for brevity’s sake?
This never got the chance to happen, but the short-lived show Threshold was going to change its name to Foothold and then Stranglehold to reflect the increased alien presence.
Tell me this is Wiki-vandalism:
Hawaii Five-O was syndicated as McGarrett.
Same thing happened with All In The Family when the focus was shifted over to the tavern and the show was retitled Archie Bunker’s Place.
Not wiki-vandalism if this site is to be believed.
Didn’t Bonanza become The Ponderosa when it went into syndication?
Don’t some reality shows change their name to reflect the season. Survivor started out has just Survivor but each new season identifies the season. Currently Survivor: Heroes vs. Villains.
I think Big Brother, and The Biggest Loser also change their names to differentiate the seasons.
Another example would be The Real World which changed its name each season to reflect what city it was in.
A couple of Canadian examples:
The Kids of DeGrassi moved to Degrassi Junior High moved to DeGrassi High moved to (I think, I didn’t really pay attention at that point) DeGrassi - the Next Generation.
There’s also a Canadian Car Show called Motoring + the year (i.e. Motoring 2000, Motoring 2001, etc)
And the aforemetioned Black Sheep.
One of the earliest examples of this phenomenon must be Make Room for Daddy, whose name was changed to The Danny Thomas Show after the first three seasons [1954-57].
The name change coincided with the actress who played Thomas’s wife, Jean Hagen, leaving the program and having her character killed off. Danny’s character courted and subsequently married Kathy O’Hara, played by Marjorie Lord.
The show (and many of its characters) was also revived as Make Room for Granddaddy in 1970, but it lasted only one season.
Actually, the show did use the name Black Sheep Squadron for first-run episodes. It was cancelled at the end of the first season (as Baa Baa Black Sheep) but was brought back in midseason as Black Sheep Squadron. (Wikipedia is wrong, but The Complete Directory of Prime Time TV Shows confirms this.)
Black Sheep Squadron was used in syndication, though.