The Western Church was generally in decline from, say, 400 to 700 AD. Yet, Clovis converted, and more to the point, so did many other dukes. In the end, the Pippinids conducted various wars with the Frisians and Saxons to crush their paganism. They even appointed bishops from outside their realm. It almost seems that their aim was to have a "Christian" land. How true is all this, and why were they so fervent in supporting a religion whose leader was getting weaker by the decade?
The thing you have to realize about France is that even though it was essentially conquered by the Franks (Germans), they were never much more than a ruling class. The common people continued to speak Latin, which over the millennium slowly became the language we today call French. We can assume they would have been inclined to keep other aspects of their culture too, and that includes their religious beliefs.
At this time most of the larger German tribes had converted too, but they generally would convert to the heretical version called Arianism*. This conveniently allowed them to call themselves Christian, but without acknowledging the authority of the Pope. Colin's argument was that by converting to the standard version of the faith, the Franks were able to better appeal to their subjects, the common people of France, as their protectors. This would have strengthened their grassroots political support.
* - No this has nothing to do with Nazi "Aryiansim". It was a minor difference over the mechanics of the Trinity, which ended up being far more important politically than theologically.