800-1000 AD. The Viking Age.
The Vikings behaved somewhat different the in OTL, due to the absence of a Carolingian Empire. They did not conquer Normandy, though they still burned down Paris (instead, a Viking became a Duke of Brittany, and some of them controlled the Frisian Islands for a short while). The Viking Storm hit Visgothia very hard, though, as a large army of Vikings burned down the nation's capital and gathered tribute until finally being forced out of their based in Lisboa in 866, after twenty years that crippled Visgothia for the rest of the century.
But the most long-standing Viking achievement was the birth of two brand new states: Kievan Rus (just like in OTL) and Viking Ireland, governed by an assimilated dynasty in Dublin. Viking Ireland (AKA Norseire) became a base of operations for further raids on Brittany and against Visgothia and Acquitania. Norseirean sailsmen reached as far as Iceland, and have heard of another island called Greenland, as well as distant myths of something even further west.
Neustria, Astrusia, Acquitania and Burgundia are still alive and "well". As they are not as overstretched as Charlemagne's empire, each one is able to take care of its own troubles... but is unable of reuniting the Frankish Empire, it would seem. Italian Empire suffered little from the Vikings, though the Berber nomads, recently converted to Islam, almost took Carthage. Italia is slightly stagnating, some say... Venice is a city-state republic under VERY NOMINAL Italian control (like in OTL, but with Italia instead of the Byzantines). The Pope does not control any real territory, but still has a lot of authority.
Visgothia is ruled by an almost-powerless king, who is a pawn in the power struggle between two main feudal houses - House Leovid and House Swanterhild, controlled by Duke of Lusitania and Duke of Asturia respectively. The reason that the king has ANY powers left AT ALL, even nominal ones, is that the two Houses are in a bitter struggle, allowing the more capable monarchs to play them off against each other.
Saxonnia and Bavaria are in control of parts of central Germany (east of Rhine, west of Oder). Further east, Sorbic Slavic tribes are dominant, and further still, there are Baltic Peoples. And then, there is the Kievan Rus...
In Pannonia, there is a new rising power - the newly-Orthodox Christian kingdom of Greater Mordovia, founded by Svyatopluk (historically a Mordovian duke who fought off Carolingian armies until being crushed by the Magyars).
Byzantine Empire is definitely recovering, having retaken the Avars and converted Bulgars and Lombards to Orthodox Christianity. In the "eastern front", it regained much of Syria and Armenia, while its Khazar allies are now threatening and occasionally attacking Persia. This was helped out by the recent break-up of the Arab Caliphate. It was divided into the Fatimid Caliphate in Egypt, Sudan and the Holy Land, the (remaining) Abbasid Caliphate in Iraq and Arabia, the Zanzibari Emirate (in East Africa - you will probably have to edit in the island of Zanzibar on Jason-NK map) and the Parsi (sometimes called "Righteous") Shiite Caliphate in Persia and parts of India. Neither is particularily stable yet, but each has many possibilities.
Finally, we have the Magyars, Khazars and Kievan Rus. The Magyars still tried to conquer Pannonia, but as Moravia was alot stronger, it fended the Magyars back. Magyars were also raiding Khazar and Rus territory, but eventually, Svyatoslav II crushed them in a victorious campaign. Magyars scattered, some of them later serving as mercenaries in Khazaria. As of now, Kievan Rus has recently been converted to Orthodox Christianity... Khazaria avoided a serious clash with the Kievan Rus, as it never switched its center of power further north, as in OTL. It is a fairly stable and prospering state (fortified by the Mandate of Heavens and a well-trained standing army), even though the Caucasian Avars (future Chechens, interestingly enough) are being rather troublesome. Khazaria is the Byzantine Empire's only trustable ally. It holds a small strip of the Black Sea coast, including Crimea, some territory stretching to the eastern coast of the Caspian Sea and including the Astrakhan/Itil area, and, ofcourse, Caucasia.