I think you're approaching this from the point of view that the people actually want to have the power to vote. Of course, there's no evidence from the time as it was never a serious question, but I doubt they would - the country's recovering from a civil war, many people's homes and crops will have been burnt, I suspect being able to vote will be the last thing on their mind, especially considering that it's a pretty alien idea. Besides which, the people were horrified at the execution of Charles I - so the question of 'defending their newly gotten gains from the Stewarts' doesn't really come into it, as a large proportion of the population, probably a majority, would support a Restoration.
Its not the right to vote in my mind that is the most important of the reforms that the Agreement of the People puts forward. Equality before the law, abolition of imprisonment for debt, abolition of monopolies and excise tax, and taxation in proportion to personnel property, are all reforms that would go a long way in improving the situation of small landowners and petty bourgeoious (sp), and thus would, I believe, get popular support for these policies. Since the country is recovering from a Civil War, these reforms would be all the more important because of the economic difficulties that the Civil War would have imposed on the common people.
I think you're overestimating the power of the New Model Army. While it was the primary military power on the British Isles, it wasn't a homogenous entity - there would be many officers who would heartily disapprove of the Levellers and act to crush them. Not to mention that, pre-1651/52, you still have to deal with the Scottish army, over 20,000 troops, which is either in Scotland or coming over the Border. If the New Model Army is supporting something as radical as the policies of the Levellers, the chances of the Scots' success under Charles II and General Leslie is a lot larger.
I address the fact that the Levellers would not be popular with a great many in the Army, that's why I'm proposing a third round of civil wars between the Leveller forces and the Army Council (Grandee) forces, as the POD.
The window for that POD is really quite small. It would really be based around two things, the organization of the Levellers into a cohesive faction within the Army, and that faction's ability to raise a significant portion of the Army in revolt. So let's say that the Levellers organize during the Putney debates, which were held in October/November 1647. The Second English Civil War happens as OTL, and the Army reacts the same way at the end of it, committing "Pride's Purge" and having Charles executed.
With the removal via execution of Charles a major Leveller plank, that the King be removed, has been completed. The execution also serves to radicalize the Army because it has made the Army into regicides and made a Kingless future, that is a Republic, the only real choice. With an organized Leveller faction now within the officer corps the desire for the Leveller's program spreads and is used to expand the Leveller faction.
When the Bishopgate Mutiny takes place the Leveller faction, fearing that they will be attacked, reacts. Leveller supporter arrest Cromwell, Fairfax, and Ireton and the Leveller leadership declares itself the new Army Council. The Leveller Army Council declares that the Agreement of the People is to be the new manifesto of the Army, and requires that all units swear and sign alliegence to the new manifesto. The pro-Grandee forces are left disorganized, with their leadership in Leveller custody. The Leveller faction raises its civilian supporters in London, taking over the city, and officers loyal to the Leveller cause raise their units in support of the new Army Council.
The coup in England encourages the already suspicious Scottish Conventer forces to reach out to Charles II for an alliance. Charles II moves up the date of his arrival in Scotland, hoping to take advantage of the unrest in England. Charles II lands in Feb 1650 in Scotland, and signs agreements with the Scots that bring them onto his side. Pro-Grandee units basically have the choice of joining Charles II or joining the Levellers. Most of the Pro-Grandee units choose to submit to the new manifesto.
The Third Civil War is fought much as OTL, with the New Model Army beating Charles in a series of battles. The final battle sees Charles II killed, and the Royalist cause across the British Isles collapse. With the Royalists destroyed the Levellers are now in control of England and Scotland, and proceed with an invasion of Ireland to suppress rebels there.
Domestic polities are now ready to be addressed. The Rump Parliament is at odds with the Army and is dissolved in favor of new elections. The Army already realizes that the elections will be difficult to carry out, and so dissolves the “Rump Parliament.” The Army Council takes over governing, and declares the Agreement of the People the Republic’s new Constitution. Elections are set to be held in 1654 under the new constitution.
During this time the Leveller leadership works to build support for its programs. When the elections come they are supervised by the Army, and Levellers dominate the first Republican Parliament.
To address the Scottish threat, though the Levellers may not be popular, but I don't think that the Scotch forces, who were trying to impose their own religious views (Presbyterianism), would be any more popular. At least the Levellers are Englishmen, who hold the same religious convictions as most the English people. The Scottish forces viewed themselves as foreigners. Charles II was able to get Scotland to unite for him because he signed agreement recognizing the independence of the Scottish church, and because the Scotch forces that had been allied to the Parliamentry forces thought that the English were going to infringe of their independence.
As for British vs English, depending upon when in the 1650s you're talking it is in a British context. Even pre-Cromwellian Union with Scotland, it would be foolish to take the idea out of a British context. The main problem with the Levellers is that Leveller control would usher in a long period of unrest and instability. Cromwell managed to gain the support of the more conservative groups in society, and that in a large part was responsible for the (relative) success of his regime. The Levellers would have alienated those groups, and it's likely that they would sponsor a restoration even more than they did in OTL.
Remember that it was the army that imposed the Republic in the first place, marching on Parliament after the Second Civil War and carrying out "Pride's Purge" on Parliament. In my reading of the period's history the reason that the Army held power was because they had the will to hold onto power. Cromwell was the mainspring of that will, and with his death the Army's leadership splintered and the Restoration occured.
With a different leadership (the Levellers) committed to Republican rule (or at least not monarchy) then I can't see the New Model Army welcoming a Restoration. In fact, with the POD and subsequent TL as presented, I think that popular want for a Restoration would be much reduced. James II would not be as easy to get along with as Charles II.