I have the same problem too. I tried to form an alliance with Spain but I couldn't, currently they have no allies but they are at war with Carthage.

Is it possible that if you wipe out a faction that was previously their allies you will never be able to form and alliance with it's former ally ever? You see I destroyed Gaul who were allied to the Spanish a long time ago. I think this could be a bug or something.