TL;DR: The two families are opposites in several ways, but the true animosity didn't begin until the Sacking of King's Landing at the end of Robert's Rebellion.
In many ways, the Lannisters and Starks have always been complete opposites. Both families were among the oldest in Westeros, tracing their lineage all the way back to the First Men. The Starks, however, were long known for their rigid honor and conduct. Their very name - Stark - describes not only their environment in the North but also their outlook. In contrast, the Lannisters were known for flexibility & deception. The family name itself is derived from Lann the Clever - a man most widely known as the trickster who conned his way into ownership of Casterly Rock.
However, much of the animosity we see during The War of the Five Kings is fairly recent. It largely began during Robert's Rebellion. Although it's possible that Ned Stark had some minor disdain for houses which refused to take a side during the rebellion, that is only conjecture at this point. He DID, however, resent the fact that the Lannisters only joined the Rebellion at the end, once it became obvious who was winning. This resentment was still evident years later.
"The lion of Lannister flew over the ramparts, not the crowned stag.
And they had taken the city by treachery." "There was no honor in that conquest." - Eddard Stark (GoT, Ch. 12)
The Sack of King's Landing
During the sack of King's Landing at the end of the rebellion, it was Ned who first breached the throne-room. Expecting a vicious battle against the Kingsguard, Ned instead found Jaime Lannister - the king's personal bodyguard - standing over the dead king, having just killed him. From Ned's viewpoint, Jaime had broken his sacred oath to the Kingsguard, killing the very man he was sworn to protect. From Jaime's viewpoint, he had a very valid (heroic, even) reason for killing the king, yet saw only judgement & scorn on Ned's face.
In addition, it seemed obvious to Ned that the horrendous actions of Gregor Clegane were done at the orders of Tywin Lannister, although he could never prove such a claim. He and Robert had a heated argument about this very matter, and it caused a rift between the two that only their shared grief of Lyanna could heal.
So, immediately following the end of Robert's Rebellion, you now have Ned Stark disliking both Tywin AND Jaime Lannister, albeit for different reasons. You also have Jaime Lannister resenting Ned Stark for his judgmental attitude.
Fifteen Years Later
The series picks up 15 years after the rebellion. When the Hand of the King - Ned's friend Jon Arryn - dies, Catelyn Stark hears from her sister (Jon's widow) that the Lannisters were behind the assassination. There is also the matter of Bran falling into a coma while the King (as well as Queen Cersei and her brother Jaime) are both present - an event that Ned views with some suspicion.
After Ned becomes the new Hand, he picks up Jon's investigation and learns of
the incestuous affair between Queen Cersei and Jaimie. Cersei also confirms that they were involved in Bran's accident.
Obviously, this happens AFTER the passage you quote, but it only further cements Ned's dislike of the Lannisters, and now gives Cersei a practical reason to dislike Ned.
It should be noted that Tywin did not necessarily share this animosity for the Starks. In fact, it could be argued that he respected Ned somewhat, although he does seem to believe that Ned's inflexibility & rigid adherence to honor was in fact his greatest flaw. In fact, the only person we really see Tywin expressing any animosity towards is his own son, Tyrion.
Note: Regarding Cersei, it's entirely possible that she already resented Ned not only because of the way Jaime felt, but also because she saw in Ned a loyalty & love that Robert never showed her as his wife. This is only speculation on my part, however.
