This might be a bug in the AI which could be supported by the AI bias of Dido. The overall feedback provided by the game concerning AI choices is poor, and often you see yourself in a situation where you can't figure out why. This is one of these situations.
But let's take a look into the different AI traits and biases. There are values in the game which influence the behaviour of the AI, in your favor or against you. This makes the AI more jumpy, especially Dido who has the highest value in the trait deceptive, along with Water Connections.
These are some of the assigned values.
--------------------------------------------------
| Dido AI Traits Trait Value |
--------------------------------------------------
| (Flavors) Water Connection 8 |
--------------------------------------------------
| (Diplomacy bias) Deceptive 8 |
--------------------------------------------------
| (Diplomacy bias) War 8 |
--------------------------------------------------
| (Diplomacy bias) Hostile 6 |
--------------------------------------------------
| (Diplomacy bias) Afraid 3 |
--------------------------------------------------
You should take a look at civdata.com for more values.
As you can see, Dido isn't quite a nice person. She usually wants to deceive you and almost always wages war. She also isn't afraid of your army, even if it's clearly superior to hers.
Because she has a hostile attitude, she couldn't stand you being nearby, that's the reason for her claim. You agreed to it. You also mentioned that your nearest city has indeed expanded, although it was naturally, you did break the promise. You acquired land nearby!
The notification claiming you hold your promise is contradictory which can mean that it could be just a bug in the end. Nevertheless, you should never expect that Dido is a nice and caring person, the moment you don't pay attention, she's in front of your city with her African Forest Elephants.
You can read more about her on the corresponding Wiki article.
One possible hypothesis is that the AI of Dido and the game itself, the diplomacy system, didn't work together.
For Dido land is equal to land, not minding the method (natural, buying, use of Great People, etc.) of acquiring it. For the diplomacy system land may not be exactly land. Probably, the game itself thinks that acquiring land naturally may be fine, so it doesn't exactly break the promise. However, Dido thinks differently, and somehow AI and diplomacy system collide which results in both breaking and holding the promise.
Nonetheless, this is just a theory, I didn't develop the game.