I agree with RP that I wouldn't immediately write him off. Who ever really knows what they're doing in relationships? Maybe he didn't quite grasp what you were willing to accept whenever you tried to bring up the topic; perhaps it made him nervous to think about and when he met this other person he fell back on his default programming of only having one at a time. I would give him a chance at least to hear him out and see if this is workable. There have been good strong poly relationships to come out of much worse situations that this! I don't think what happened is such a huge failure.
Oh, and to say he's "only" had relationships that have never gone past five years made me giggle. Before I got married at age 39, my longest-ever relationship was three years - and that was when I was in High School. All my adult life, I never had any relationships last even a year. That doesn't necessarily mean anything. The most important things are how you communicate and treat each other. This can be turned around, methinks.