I've read many times, both here and elsewhere, that the period following the fall of Rome, whatever you want to call it, did not in fact experience slower scientific, technological, and cultural progress than the periods before and after. It would be easier for me to convince myself of this if I could picture some specific things that those medieval peoples could do that would have left the ancient Romans or Greeks scratching their heads. (This may sound to you smarties like a childish way to understand something, but I'm a dumb engineer, and this is just how my brain works.)
As this question is motivated in part by my having gathered that the concept of "dark ages" is now widely considered to be pseudo-historical nonsense, and as my mental image of the dark ages is in Western Europe prior to the 12th-century renaissance, I'd prefer to avoid post-12th-century stuff or stuff going on over in the Byzantine Empire (which I understand was a direct continuation of the Eastern Roman Empire).
I also have noticed that expressions like "A is more advanced than B" can be controversial, so let me define this as meaning specifically "A has the ability, if he wanted to, to do something B could not do even if he wanted to", where that "something" could also include just greater efficiency or whatever.
There were three important agricultural innovations which (sort of) fit your time period.
One of the biggest changes in agricultural technology would have been the introduction of the mouldboard plough.
The mouldboard plough had two advantages. It greatly reduced the amount of time to prepare a field, allowing a farmer to farm more land and grow more produce. In the form of the heavy wheeled mouldboard plough (sometimes known as the "Roman Plough"), it also allowed tougher and more difficult soils to be ploughed and put into agriculture.
There is archaeological evidence that the Roman plough was used in Britain by about the late 3rd or early 4th century AD. So, it came in in the Roman period, but very late in the Roman period.
By the 8th or 9th century, the three field system (one field planted in grain, one in other crops (usually peas, lentils or beans), and one left fallow as pasture)- rotate annually - had replaced the old two field system (half the land left fallow every year) in Britain. (The secret to it's success was planting the third field in nitrogen fixing crops, which helped renew the soil.) This meant that the farmer could produce more (produce from 2/3 of his land, not just 1/2), than previously.
The replacement of oxen by horses as the main draft animals for ploughing came later in Britain (12th century? So, right near the end of the period you are looking at.) This was a result of the introduction of the horse collar, which allowed horses to pull ploughs (oxen had used an ox yoke, but this did not work for horses). This led to another improvement in farm productivity, as horse teams can plough faster than ox teams. (Raising Crops in Northern Europe, with a short growing season, means that there is a limited time between the ground thawing and the crops needing to be planted, in which ploughing can be done. What cannot be ploughed in that window cannot be successfully cropped that year).
These three innovations allowed more land to be planted, and allowed a farmer to grow more than farmers had been able to in ancient Greece and Rome.
Both the wheelbarrow and the chimney are first recorded in western Europe right around the end of your specified time period, in the late 12th century.
The Chinese have had wheelbarrows since at least the second century. Some historians speculate that while some written evidence suggests the classical Greeks may have had a similar technology, there is currently no archaeological evidence. The first wheelbarrows in Europe are recorded sometime in the 1170-1250 period. I don't think the wheelbarrow would have blown a Roman's mind. It is a pretty simple device and while incredibly useful it would be hard to argue for a measurably large societal impact from the introduction of the wheelbarrow.
Chimneys had a possible Roman counterpart in a tube-system used in bakeries. It was not until the late 12th century that large buildings in northern Europe began to incorporate specialized smoke ventilation shafts for domestic fireplaces. Seemingly unassuming, it is possible that the chimney had a much larger impact on medieval society than, for example, its contemporary the wheelbarrow. In Barbara Tuchman's A Distant Mirror the author mentions how this development revolutionized the social atmosphere of a manor house or castle, since the lords could retire to the solar, heated by a private fireplace, rather than sleep in the main hall with the central hearth. It is possible that this contributed to the stratification of high medieval society, as lords and ladies retreated to their private residences, abandoning the common rooms of their retainers and hirelings.
In direct contest to the OP what are some specific examples of what was lost? I remember hearing that a lot of medical knowledge was lost in western Europe after the fall of the Romans.
You're not wrong to see the High Middle Ages as a time of renewed economic and technological growth. But that's less because everyone was stupid for five hundred years after Rome, but because Europe was a mess, composed of small, fragmented polities prone to invasion by outside groups (Avars, Magyars, Norse, Berbers, etc). Traditional trade routes with the east were frequently disrupted, meaning that what goods Europeans had to trade were more difficult than ever to exchange. In this unstable and chaotic environment, with a depleted population and a culture that was, largely, far more rural than the urban-oriented civilizations of Greece and Rome, it's not surprising that stagnation occurred in certain areas. If your largest city has a population of 10,000 people, and almost all your subjects live hand-to-mouth in small villages and on farms, it's not really necessary to build aqueducts or plumbing or coliseums.
You can certainly trace improvements in military technology during the period. Off the top of my head, these include the manufacture of longer swords using better metallurgy; longer and more protective coats of mail (Roman mail tended to be T-shirt-like, rather than the long coats common by 1000 CE); dished steel helmets (Late Roman iron/steel helmets - spangenhelms - were multi-piece construction); improved high-cantled saddles; and shields better suited to cavalry warfare. Most of these are not really revolutionary but evolutionary advances.
Other, less militant innovations include Carolingian minuscule (an immensely useful standardized Latin script), the establishment of universities, and the watermill (extremely useful to agriculture). Other developments came into Europe by means of cultural diffusion; but that's not at all uncommon, and, in my opinion, shouldn't be counted against them. It's not surprising that they cribbed from the Byzantines, the Arabs, and the Chinese, areas with far larger populations, stronger economies, and much more centralized government.
This may be violating rules (in which case I'll edit), but I'm going to provide a quick overview of examples, along with one or two that I'll go into depth on.
First of all, the concept of "scratching their heads" is a difficult one, as you rightly point out in your post. Ancient technology, in general, was very different than how we think of modern innovation. Certain metallurgical techniques and construction methods would perhaps baffle someone from a few hundred years earlier, but by and large, advancements in technology were characterized by thinking of new ways to use existing technology or building a simple machine. Once built, they were fairly easy to copy. In /u/mormengil's example, one of the reasons that the mouldboard plough spread so quickly was that it was fairly easy to reproduce. Had it been introduced to the Romans of the Punic Era, they would have quickly grasped its purpose and adopted it. I use this in contrast to perhaps showing an iPhone to Abraham Lincoln and asking him to understand how it works - he'd certainly be scratching his head.
The real issue with understanding this period is that there are very few strong sources - from 500-1000, you're really looking at either archaeological evidence, Ammianus Marcellinus, Procopius, and I'll add in Ibn Fadlan as well. At that point, you begin to look at monasteries copying manuscripts, which is valuable in its own right but produces less original work.
As I said, I provide a few innovations below that I can't go into depth on in case it invites an expert in the field to join in (my specialization is in Late Republican legal work and Early Christian thought). If these aren't permitted I'll remove them. I can source every claim I make below:
Military innovation - this is mostly stylized. The Eastern Roman Empire was virtually identical to the West for a while, but gradually adopted military traditions from their neighbors. For example, the comitatenses of the Late Western Empire employed mail armor, while the East gradually adopted lamellar armor (scale armor). It had been around for hundreds of years; the Romans just didn't use it until this point. Likewise with the composite bow, borrowed from their Eastern neighbors.
In terms of construction, I did a bit of quick research and it seems that a chief innovation in the pointed arch, which many attributed to the arrival of Islam, but in actual fact seems to have been developed or at least employed in the 6th century AD. I really don't have the background to place this into its proper context, but it was certainly a mid-millenial development.
I'm going to post this in the hopes that it inspires a few people to contribute, but I'll come back and edit.