Maybe you could fiddle something with the Dukes of the Vascones in Carolingian times? Charlemagne is a major historical legend underpinning the Reconquista (though most Spanish kingdoms hark back to Visigothic royalty), but the image of the Franks is hardy untarnished. If the Chanson de Roland is turned on its head, making Charlemagne an aggressor who uses the weakness of his Christian brethren facing the infidel foe to his own advantage by stabbing them in the back... Would make the Basques look a bit better.
The Basque princes, tracing their ancestry back to the Duces Vasconum, claim the oldest blood in Spain and their fighting men carve out their territory along the Ebro valley. Aragon is stunted, and while the majority of Spain's territory still falls to Castile and Leon (and Portugal), the Ebro valley and the coast down to Valencia is now part of the Duchy (from 1176 kingdom) of Vasconia (Navarra, roughly). The Duchy of Barcelona (with most of Catalonia) falls to France. It would very likely still be a multilingual country with a Romance-speaking upper class and a large Basque-speaking rural population (interspersed with Arabic- and Berber-speaking enclaves), but Basque would be regarded as a noble heritage of the nation rather than heathen yokel talk.
But the wars with Castile and Leon will be awful...