Theres no such thing as the Kingdom of Tolosa, it was part of the Roman Empire, then the Visigothic Kingdom (who had their capital at Toledo to the south). They ended up having a succession crisis that led to Toulouse not even being in the Kingdom of the Visigoths anymore (the so called Kingdom of Toulouse, ruled by a pretender to the Gothic Throne), they ended up getting conquered by the Duke of Aquitaine (partially, the capital Narbonne was taken by the Muslims), who was Frankish. The Carolingians did not rename it, and stating it like that suggests that Charlemagne himself was behind that, when Odo mostly fought his Grandfather Charles Martel. What Charlemagne did due was make his son the King of Aquitainia, probably to let him establish a power base amongst people that revolt every time their ruler (as they did when Martel and then Pepin died) dies, gotta cut that in the bud.
Anyways the requirements for them should be more Spanish, their capital and the majority of their land was in Iberia, according to the Councils of Toledo (the main religious meetings or synods of the Visigoths) the Archbishop of Toledo was the head of the church in the Visigothic Kingdom. Occitians are a mix of what was left after the succession crisis and various other infighting and the falling apart of the Kingdom to Islam and the Franks, who make up the other portion of the mix. The Spanish Kingdoms in the north on the other hand represent the actual remains of the Gothic Kingdom, most of whom trace their lineage to Gothic ancestors instead of Frankish ancestors, especially by 1066. The first hereiditary count of Toulouse was a "opponent to the interests of the Visigothic nobility" (yes its a wiki quote, not gonna give a long speech but every page is basically an essay, if the sources are good they should be good, the sources are good for
http://en.wikipedia.org/wiki/Bernard_of_Septimania note that being from Narbonne is considered more important than being count of Toulouse), the Dukes of Aquitaine claim descent from Charlemagne himself. The Spaniards on the other hand nearly had a war in the 1400s with Sweden over the actual title of King of the Goths. The House of Barcelona is descended from the Belonids, who were a Gothic tribe. The Kingdom of the Visigoths being Occitian just doesn't make any sense. What the French did have was a title for the guy who ruled around Narbonne/Septimania, the Duke of Gothia. His job was more keeping the Goths in (peasent and minor nobility) in line and making sure the south was loyal to the north. More a "we rule over the Goths" than "we are the Goths" title, I doubt Goths would appreciate it.
Also Saxony was a Kingdom, Charlemagne warred with it for about 40 years, his Grandfather fought it as well. It was never a Christian Kingdom, one of Charlesmagnes policies was sending the Saxon populace throughout the rest of the Empire, not unlike how China is making Tibetan a minority in Tibet. Very decentralized though. The Spanish March was never a Kingdom, it was a March, ruled by a Marquiss or Margrave, which is inbetween Count/Earl and Duke. Should have a few, Roland was the Marquiss of Brittany, the Osterreich (which was never a Kingdom and the Austrian Empire was formed in 1806, Austrian Hungarian in the 1850s, sorry, but many of the titles make no sense in this time frame. Prussia as well, they only rarely referred to themselves as the Kings or Kingdom of Prussia, it was usually King IN Prussia, to not piss off the Kaiser who gave them the title in exchange for help, Prussia itself not being in the Empire, the Duchy being descended from the Teutonic Order by way of Poland) gets some of it's prestige from being on the border (literally means Eastern Realm) as it is, defending against those that might come, specifically the Slavs. Brandenburg was a Margravate at one point, until the Wendels died down, or off.
Anyways, for suggestions,
http://en.wikipedia.org/wiki/Uí_Ímair they had some really cool titles, some of which you covered. Always really liked the sound of the King of Foreigners myself. King of the Vandals would be pretty cool, based out of Carthage, actually what led me to this mod was a desire to play the Alan King of the Vandals (and Alans, which is why I picked Alans, that and their retinues are good and I spent money on the facepack and am tired of Russia). High King of something maybe, although properly that should probably be the Celtic replacement for Emperor. North Sea Empire, probably using the Raven flag as a symbol. possibly the Angevian Empire.
Overdid it a tad in places like Kent and Essex, those actually are already in the game. Not all Kings are equal, in Britain High Kings ruled over Kings until they decided to call Kings Duke (or Earls) and High Kings Kings. As long as there has been a Kingdom of England the Kings of the Heptarchy were subservient to him (except for when Vikings beat them), you should consider somehow making titular duchies called the "Kingdom of Kent". Whatever, it's a game and doesn't have to 100% accurate, it's just that right now it is closer to 0% accurate.