All of the anime that 4Kids dubs usually have a different theme song than the Japanese version. They also usually play an instrumental version of the intro song instead of the ending theme
Any anime shown on Nick Jr. in the 1990s will have this.
In Italy, pretty much every anime gets at least one if not more (especially the ones airing on any Mediaset channel). In particular, Italian singer Cristina D'Avena is famous in Italy for performing alternative theme songs for hundreds of different animes in the 90s and early 2000s.
Practically any anime that aired on the former French block "Club Dorothée" had this.
During the Dark Age of Anime in France, most shows got a French opening, many of which (but not all) are now considered So Bad, It's Good. French singer Bernard Minet is now more remembered for this than for any independent song.
For the case of Ponyo and Arietty, a dubbed version of the original song used in the credits is played for a few minutes, (For Arietty, there was an English version of "Arietty's Song" along with a French and Japanese version when the movie came out in Japan) then the new theme song plays for the rest of the credits.
And finally, the Korean version. Not only did they make that song in Korean, they did it in English, too!
The 1979 Cyborg009 anime got a Finnish dub in the 90's, which included an entirely new opening. This is particularly interesting because Finnish dubbing companies usually never do that - in fact, at the time it was pretty common for dubbed anime to air with the original Japanese opening and ending themes.
The upbeat J Pop song of the Deltora Quest anime was replaced with a dramatic orchestral tune for the English dub. Arguably it actually fits the medieval-ish swords-and-monsters setting of the series much better.
Every Digimon English dub has used entirely new theme songs. The dubs of Digimon Adventure through Digimon Tamers used an action-packed rap song with minor alterations, while Digimon Frontier received an epic chant and Digimon Savers received a rock song. With the exception of the Savers one, all the dub themes feel very thematically different from the Japanese counterparts, which generally all fell into the category of upbeat rock songs. This generally extended to the licensed video games as well, which tended to use versions of the Japanese anime themes which were accordingly changed in translation.
FUNimation's in-house dub of the Android/Cell sagas had it's own opening / closing that were instrumental tunes set to random clips from the show. The Majin Buu era did somethingsimilar, but based it's footage around the Japanese opening/closings. When FUNimation went back and redubbed the Saban episodes, they used this. Recent DVDs keep the Japanese opening/ending footage, but replace the songs with instrumental tunes not related to the original songs.
The Westwood English dub of the second half of DBZ for Europe and Canada even did its own rendition using the video footage of Rock the Dragon.
Their dub of Dragon Ball GT with Blue Water got its own theme song using footage from the original opening.
Their dub of the original Dragon Ball (also with Blue Water) got a rather childish Canadian opening based on the French theme that the UK broadcaster found so embarrassing, they made their own opening theme.
The French dub of the Dragon Ball series used several original songs that were completely original to its dubs. Dragon Ball and Dragon Ball Z each used had different openings.
The European Portuguese dub used the French themes for DB and DBZ as a base for both the theme and the lyrics. The dub of Dragon Ball GT (of which there is no French version) uses the original rhythm, but the lyrics are based on the previous dubs, resulting in What Song Was This Again?.
Inverted with Eden of the East — the Japanese broadcast used "Falling Down" by Brit Pop band Oasis as the theme, but FUNimation replaced it with a Japanese song in North America for all-but the first episode due to music-clearance issues (namely, that there was no way they'd be able to afford having the song appear more than once; frankly they were lucky to get to use it once).
The Japanese version of Kirby of the Stars is a cute little marching theme. The American version is an over-the-top jazz song.
Lupin III has several different openings in Italy where it is quite popular. The first, the second with an accordion theme, the third and most famous (when the series aired on Mediaset), the fourth and most recently the fifth (which actually aired before the series premiered in Japan).
The first opening theme for the English dub of Naruto was this, but afterwards, all the theme songs were the original Japanese ones.
While most dub song switches are met with hatred, this one seems to be a bit of genius as the original probably wasn't catchy enough to market the show to a new audience. This bit of genius is seen again when instead of airing the third opening, they just reused the second one while switching out some animation frames.
An instrumental theme of Naruto has been made into an Arabic opening, with added lyrics.
It's easier to count the countries that didn't use a new theme song for Rose of Versailles. This is most likely due to the show receiving a new title overseas, Lady Oscar. What gets funny is that the Japanese theme is suitably dramatic and somber, while many of its dubs chose cheerful and happy theme songs...despite the content of the show still concerning the tragic lives and deaths of people living through the French Revolution. Even more amazing? The actual French dub probably has the perkiest song of them all. Italy has twodifferent version of opening.
The Cantonese dub released in Hong Kong used a unique song for the first series. Later series used remixed Cantonese versions of their Japanese counterparts.
The entire Portuguese dub used a unique song, "Luna Luna," that was based instrumentally on the Japanese "Heart Moving" (used for the first ED of the anime) but had completely different lyrics.
While many dubs remixed or redubbed the original "Moonlight Densetsu" theme song (though the lyrical content tended to vary wildly), of special note is The '90s North American dub, "Sailor Moon Theme", which uses the basic melody but is completely different in content, length, and instrumentation.
The English dub of Yo Kai Watch originally used a peppy dance tune as its theme song in a trailer, but this was ultimately subverted as they ended up dubbing the original opening theme and ending theme instead. The song wound up being used for the video game instead, but later played beginning in episode 10, and alternated with Gera-Gera-Po to be used every other episode, like the two themes used in the Zeroshiki arc.
Various anime that aired on German TV station Viva happened to have different openings. Among the more notable are X1999, which uses "Mother Earth" by Within Temptation and this kickass metal song for the Hellsing tv anime.