Why was the Roman Catholic Church so powerful during the Middle Ages?

The Roman Catholic church was powerful because it was the only major institution left standing after the fall of the Roman Empire. It had a pervasive presence across the European continent.
It became a repository of knowledge, maintaining (to the best of its ability) the wisdom of the Roman Empire. It preserved Latin as the universal language of the educated classes, unifying a fragmented continent. It also became an important legitimizing force for those seeking power. Kings and princes sought the blessing of the pope to authenticate their right to reign, and excommunication became an important tool for controlling rogue monarchs.
The pope had a papal army, and the land holdings of the church were far-flung but were all controlled by one unified institution, giving the church a powerful economic base on which it could draw.
Belief in Christianity was a unifying force that brought together people of various social classes and nationalities. By encouraging pilgrimages and donations, the Church also consolidated wealth and power.
It also helped enormously that the Catholic Church was the only legitimate religious institution during most of the Middle Ages, having a monopoly on religious authority as the sole voice of the divine in this period.
As more institutions (including, most significantly, the nation state) consolidated power, the Roman Catholic Church lost strength, especially as many countries chose to support rival Protestant denominations after the Reformation.

Between the Fall of Rome (476 CE) and the Protestant Reformation in the sixteenth century the Catholic Church was the major economic, political, and social force in Europe. There were a number of reasons for this.
Economically the church was a major landowner, and the overlap between the feudal nobility and the clergy was pronounced. Many of the manorial nobility used the church to increase their legitimacy. It was quite common for the bishop of a given diocese to also be the wealthiest nobleman in the region. This early interconnection between the nobility and clergy only continued as the Middle Ages progressed. Consider as an example Louis I in France, otherwise known as Louis the Pious. The development of monasteries also reinforced Church power, and many monastic enclaves were commercial hubs, producing specialized goods and becoming economic engines.
Politically the church had a major influence, which can be particularly seen during the time of the Crusades. The church received major support from certain potentates during the Crusades, and as a result of Crusading activity some church orders, such as the Knights Templar, became very powerful.
Socially the church became a unifying force and the elite used Christianity as a tool to conquer and co-opt the common people. The construction of churches and eventually great cathedrals in the high Middle Ages is a testament to the force of the Catholic Church in Europe. They even played a significant role in the establishment of some of the earliest universities.

After the fall of Western Rome in 476 CE, Europe lacked a strong empire to unite the people.  Instead, there were many smaller groups and tribes, such as the Franks, who ruled over their respective domains.  One particular Frankish King, Clovis, wanted to unite several of the groups within the boundaries of modern day France.  In order to do this, and in order to grow his military to the size necessary for conquering an empire, he allied himself with the only surviving institution in Western Europe from the fall of the Roman Empire—the Catholic Church.
Allying with the Church enabled Clovis to do two things.  First, he used the economic power of the Church to grow his empire.  Second, he used his alliance with the Church in order to convince other groups, who were loyal to Rome, to join his new Merovingian Empire (remember—Rome converted to Christianity in the 4th century under Emperor Constantine).
In the 8th century, the Franks and the Church faced a new threat from the South—the growth and expansion of the Islamic Umayyad Dynasty into Spain.  At the Battle of Tours, 732, Charles "the Hammer" Martel defeated the Muslims in Spain, opening the doors for a Frankish Empire in Western Europe.  This was realized by Charlemagne and the Holy Roman Empire.
The Holy Roman Empire, under the auspices of the Roman Catholic Church, conquered and united much of Western Europe.  With this, the Church maintained power over much of medieval life.