What a great thread!
Here are my few coppers:
But first, a note on plagues: the 7th century was a terrible time for plagues. The Black Death first hit Byzantium in the 6th and 7th centuries. "Justinian's plague" was key in frustrating the already ill-conceived reconquest of the West. Secondly, major epidemics almost always result from the same thing: intensive animal domestication. Societies which keep domestic animals at close quarters are more likely both to suffer epidemics themselves and to have a higher resistance to such epidemics, often being filthy and contagious. American cultures did not domesticate animals heavily and did not live with the animals at close quarters when they did -- thus, they were especially susceptible to the various plagues which ripped through the continent from 1500-1900.
1. What kind of state would Rome be?
So much of who Rome became was predicated on their conquest of Greece: their respect for the rule of law, their philosphical and theological sophistication, etc. In many ways, Rome without Greece isn't even a fully imperial power; it's simply the best organized group of barbarians. Furthermore, so much of the imperial Roman basis economically and logistically was the use of the Mediterranean Sea as the empire's mechanism for transporting goods.
I would therefore suggest that Rome might, when it encountered the Germans, find it had much more in common with them than in our timeline. I therefore see Rome developing into a political formation more like the early Holy Roman Empire: a loose Italo-German federation with the Alps at its centre. I would suggest that the empire's ideology would be highly ascetic (stoicism being the only indigenous Roman philosophy) and disciplined.
I would see the Roman Empire as having three main parts:
Italy: the ascetic agrarian urban civilization
South Alps: a heavily militarized territory in northern Italy dominated by German-speaking allies with a pastoral economy
Germany: the sparsely settled lands of Rome's Germanic allies
These lands would regularly raise armies that would march overland to demand tribute from Iberia and Illyria who would produce most of Rome's luxury goods.
Politically, I see this state as sort of like Russia: a brutal autocratic regime based on a national ideology of militarism and self-sacrifice with little concept of the rule of law.
Wildcard: Such a Germanic alliance might lead to early development of cavalry units. I would argue that the horse, not the trireme would become the basis for Roman military dominance.
2. Who would Carthage be?
Without the security of the Mediterrranean under the control of a single power, Carthage would probably continue its Atlantic rim expansion. I would suggest that they might develop an Atlantic coastal empire in a narrow band along the Atlantic Coast including modern-day Cornwall, Brittany, Bordeaux, Spain, Portugal, Morocca and Western Mauritania. There is also some scholarship about them having reached the Sargasso Sea; it might be quite exciting to give them colonies in Bermuda, Hispanola, the Canaries and the Azores.
The Carthage I imagine would therefore a kind of Semitic-Mediterranean-Celtic amalgam with African influences. I think one could make Carthage more like the actual Rome: the multi-ethnic pluralistic empire with people of all colours and ethnicities but lacking the strong trade and administration Rome had, except in the core areas of North Africa and possible colonies in the formerly Phonecian territories in Palestine.
I have no idea of what the Carthaginian religion was like so I have a little difficulty figuring out how the state would see itself.
3. What would be happening out east?
I would argue that monotheism and orthodoxy are naturally desired in cultures that are highly heterodox and pluralistic for a long time. Thus, I would argue that Egypt and Greece, after a thousand years, would be especially vulnerable to the rise of monotheistic religions.
There are a number of possible sources for the monotheistic movement: (a) Egypt -- one could argue that Ikhnaton's heresy could be ressurrected in Egypt and spread elsewhere; (b) Persia -- most people think that Ikhnaton's heresy was a modification of Persian Zoroastrianism; (c) India -- monotheistic heresies begin to emerge in India by about 600 BCE -- any one of them could conceivably move west, the most likely being Buddhism which came into existence around the time of Christ.
Which version of monotheism challenges European/Aryan civilization must, to some degree, be determined by how things have shaken down in the Babylon-Persia-Greece-Egypt conflict.
In my version, the following would have happened: the Sassanid Empire's rise would have, in fact, proceeded more spectacularly as it would be bordering decayed and backward post-Alexander Greek and Egyptian states, along with an atrophied Babylonian Empire.
I would therefore envision the Sassanid Empire as taking all of Asia Minor and the Middle East, imposing a monotheistic fire worshipping faith on the people. The Sassanids would be in the middle of the Sinai and the Bosphorus, trying to overcome these significant natural ecological boundaries in order to mount their assaults on Thessaloniki (the Greek capital) and Alexandria (the Egyptian capital). These two exhausted states would probably be in some kind of federation against Persia and would be especially susceptible to Roman and Carthaginian pressure and extortion.
4. What would be happening up north?
In my scenario, Rome has become the leader of the East Germanic tribes. These tribe would probably be engaged in ongoing war with the Franks, Saxons, Jutes, Angles, Danes, Geats and Swedes.
Further east, however, the big story of the 6th century was the massive Slavic migration into Central Europe. These primitive agrarian pastoralists would be pouring into the region, harrying the eastern border or Rome and the northern border of Greece/Macedonia. The Slavs arrived on such a large scale due to the migration of central asian peoples into the pontic steppe: Bulgars, Khazars, Avars, Huns, Pechenegs, etc. These asiatic peoples were of widely differing technology levels but were militarily superior to the primitive slavs.
This would make for a terrible situation in Illyria and Pannonia which would see the Slavs invading the frontier region between Rome and Greece. I would imagine that as in actual history, the Slavs would mostly ally with Greece as their continuous march into Germanic territory would make it impossible for them to ally with Rome. Thus, 6th century Illyria and Pannonia would look much as they actually did: weak Slavic buffer states nominally allied with Greece and dependent on them for aid.
I'm not too sure what to do with the asiatic tribes at this point: however, they could be a potent destabilizing factor in the region, threatening Greece, Rome and Persia.
5. Out west?
I'm not sure what the actual plan is here. I would suggest that the culture most suited for this new role is probably the Mississippian mound-building culture that existed through the eastern continental US until about 1000 AD. We know little about this culture except that their styles of urban planning and religious observance more some resemblance to the Mexica and other groups we identify with Latin America.
I would recommend that the culture be based around an extension of the Huron custom of the domestication of bears (they could carry whatever special plague bears are just waiting to give us). I would suggest that the culture could be an amalgam of the Iroquoian and MesoAmerican indigenous cultures with sophisticated theology, astronomy, theories of government and urban planning but still be a stone age culture. In my vision, they would have arrived in Europe via the same route the Vikings took to America: around the Atlantic Rim. The superiority of American agriculture and urban planning could have led to an overpopulation of the northern woodlands resulting in emigration to peripheral European territories. I would suggest that their first really big foothold in Europe would be the Celtic Britons promising them whatever land they could drive the Saxons off.
There are many cultural affinities between the Iroquoian and Celtic worlds in terms of mythology and political theory -- given that the 6th century is when Arthur is supposed to have lived, and given that the Dux Bellorum concept is shared by the Iroquois, I could see a different sort of Arthur: an American Arthur uniting the Britons and Mississippians and Britons against the Germanic invaders. He could also be a British Glooscap: the strange god from far away who comes up out of the sea with his flying canoe.
Perhaps another technological advantage the Americans could have in this world is a better understanding of and proficiency with magic.
Anyway, I'm sure I'll think of more but that's off the top of my head. Hope it helps.