As Dathi THorfinnsson said in his second point there will probably be too many butterflies to fufil all the requirements of the OP (a POD after 1781 with a province of New England as part of the Confederation of Canada on July 1, 1867). However, lets take out the AH bug-spray and see what we could do. From the scenarious posited, it seems workable in theory, although we all know that an alien space bat probably swooped in for some fun. I've thought about and I 've tried to combine the best elements that I've seen so far from Alratan, Dutchie and Nicomacheus. So the main points of any attempt would need to (1) provide a reason for the New England states to collectively want to leave the United States and become reconciled to the monarchy again (the earlier the better) and (2) still provide a reason for the British North American Colonies to wish to unite as they did in 1867 (which requires a strong United States and preferably one that has been militarized following a Civil War). So:
In 1781, the United States was still acting under the Articles of Confederation and the state claims in the west had not all been ceded to the United States in Congress Assembled (USCA). So as Alratan says,
Better, to have the Continental Congress disintegrate into acrimony and the colonies effectively go there own separate ways, although remain technically united, during the 1880s. The individual states retain their claims to the north west, and squabble amongst themselves over the issue. This sometimes reaches the level of minor skirmishes between state militia, but these don't escalate. By the mid 1790s, the New England states have got the sharp end of the stick several times, and have essentially lost their claims in the north west to New York and Pennsylvania. The campaigns against the British backed Indians have gone noticeably less successfully than OTL. They have been prosecuted by the state armies of New York and Pennsylvania alone, as the Congress has refused to call up Continental forces.
Citing non compliance with Article 5 of the Treaty of Paris by the United States, Britain refuses to hand over border forts in the north west territory, and persists in supporting the Indians. Representations over the issue by the Continental government are weak, given how weak and divided the body is.
Matters with Britain come to a head in 1795 [would change this to 1791]. Rather than negotiating with the Congress, a strategy of negotiating with individual states is adopted. The New England states have no particular remaining animus with Britain, so opt out of the argument, dealing independently.
The Continental Congress gets its act together for the final time, and expels the New England representatives and declares war on Britain. Despite the best endeavors of Pennsylvania and New York, the neutrality of the New England States is accepted [would change this to having the New England states neutrality not being accepted by the Continental Congress because of the endeavours of Pennsylvania and New York (the latter possibly having designs on Vermont still)]. This is particularly foolish compared to OTL, as the *Girondists where not overthrown, the French royalty not executed, and Britain not at war with France [in the period 1791-1792]. The price the southern states extract from the remaining northern ones is war with Spain in alliance with France [hmmm...Spain went to war with France in 1793, but it could be possible that Spain and the United States would go to war over the West Florida boundary dispute where Spain and Georgia/the US claimed the southern half of OTL Alabama and Mississippi, that dispute wasn't settled until 1795 so perhaps Britain convinces Spain to join the war over the disputed area or Spain goes to war with the US after the US attempts an alliance with France].
Here though, I would make changes, such that the neutrality of the New England states is not accepted (through the efforts of New York (which might still hold designs on Vermont) and Pennsylvania). I would also have matters coming to head with Britain in 1791 instead of 1795 as the French royals were executed in 1793. This leads to the United States declaring war on Britain and "her lackeys" in New England who they claim are allowing supplies to reach the British and the Indians. The Americans merge their forces into the Continental Army which fights the British in the northwest and also invades the New England states and razes several cities including Boston, Hartford, Plymouth, Concord and Providence.
As the Americans have to fight in New England and the northwest though, the British eventually get the upper hand since the American forces are split and since Britain faces no other enemies from 1791-1793 and are able to blockade the American coast (but obviously not the New England coast) and manage to get Spain onboard to open up another front for the Americans in the south around the Floridas and Georgia and contribute to the blockade after the Americans attempt to get an alliance with France to fight Britain. When 1793 rolls around and Louis loses his head in France, the war in the Americas gets absorbed into the French Revolutionary wars with the basically the rest of Europe now refusing to trade with the United States over its continued alliance with the regicidal French revolutionaries (so no trading with the Dutch). In 1793, the Americans are driven out of New England (with New York being occupied in the process) and have been fought to a stalemate in the northwest (by the British and Indians) and southwest (by the Spanish). The Americans, Spanish, New Englanders (who are all still 4 independent states now but under a New England military alliance) and British come to terms of peace: (1) The British evacuate New York and some forts, but keep others (e.g. Detroit), (2) The Spanish and Americans split the disputed territory in the southwest and (3) the Americans drop all claims against the New Englanders and Indians and (4) the blockade of the United States is lifted.
The revolutionary wars return to Europe (and to those French colonies in the Americas) and the United States returns to peace with 4 less states and having fought an unsuccessful war. As a result, anti-British (indeed anti-European sentiment minus the French) increases in the United States and a second attempt at fixing the Articles of Confederation is undertaken (it is assumed the first attempt didn't produce the OTL US Constitution of 1787 but actually just made a few minor changes). This second attempt in 1793 produces an entirely new document which is pretty similar to OTL Constitution but with a few changes to reflect the difference in thinking in 1793 as opposed to 1787 (not a great deal, but the Bill of Rights is incorporated entirely into the body of the original constitution and maybe a few clauses such as the Right to Bear Arms Clause and Territorial Clause and Statehood Admission Clause are clarified).
In the New England states, many begin to harker after the peace and tranquility that had been previously enjoyed before the American Revolution, having now suffered two wars in the space of 17 years (with 7 of those years being war years) and having had their cities razed by the supposed "republican brothers" from America. During the war, the New England states had formed a military alliance which by 1793 had morphed into a Commonwealth of New England (CNE) - which is the third New England union following the original New England Confederation and the Dominion of New England in America in the late 1600s. Soon thereafter the New England states began debating rejoining the British Empire and their individual governments, as well as the Commonwealth government had many debates, but it was finally agreed that New England should remain independent, while seeking an alliance with Britain. It would have been all for the best anyway, since King George III didn't much like New England privately and thought of them as spoilt children who couldn't make up their minds (having first led the rebellion against him 17 years ago and now contemplating a return to his dominion), he did however agree to a military alliance in public and privately was delighted at the prospect of having a pawn in the North America to help counterbalance the United States. His son however, held no ill will towards New England.
Life goes mostly as it did from 1793 until 1811 with the exception that the United States doesn't include New England and eventually will have 2 or 3 more states formed out of the northwest territory and 2 less slave states admitted although the concerns of balancing the free and slave states wasn't profound until after 1812. Only 1 slave state was admitted after 1792 and that was Tennessee in 1796 which was balanced by Ohio in 1803. Kentucky and Vermont had balanced each other out in 1791/1792, so now with Vermont and the other 4 New England states gone, the balance (in 1793) would be: 9 Slave to 1 Free (compared to OTL 9 Slave to 6 Free). By 1799 the balance would have shifted back to what it would have been before 1791 with 8 Slave to 3 Free and then 8 slave to 4 Free in 1803. The admission of Louisiana (the Louisiana purchase still goes through) would be delayed until 1819 after Indiana and Illinois were admitted bringing the ratio to 8 slave to 6 free and then 9 slave to 6 free. Thereafter a few more states would be formed out of the former northwest territory and upper louisiana purchase in order to bring the balance up 9 slave to 9 free by the mid 1830s.
However, before any more states would be admitted after Ohio in 1803, the United States would find itself again at war with Britain (and New England) in 1812. The War of 1812 starts much as it did in OTL and for the very same reasons (none of which would have been addressed by the 1791-1793 war). The War of 1812 progressed much as it did in OTL for similar reasons, although it started out with Americans taking fort Detroit and then moving into Upper Canada. The Americans also attempted to move into Lower Canada through New York while at the same time invading New England (once again). This time the Americans razed Hartford, New London, Providence and heavily damaged parts of Boston in the Siege of Boston (which was relieved by a British force coming from Lower Canada). Once again the Americans were pushed out of New England and New York was threatened, but the British and New Englanders didn't besiege it. Washington D.C. was burned in 1814 by the British as York (in Canada) had been burned a year earlier by the Americans. Finally in 1814 a peace treaty was signed (no attempt was made by the British to land at New Orleans as they had force commitments in New England to prevent the Americans returning) and it was ratified in 1815. In the treaty the British evacuated fort Detroit in exchange for some territorial adjustments in the northwest around the Lake of Woods (both areas had been occupied by the United States and Britain respectively, so it just legalized what was already the situation on the ground). After the peace treaty the British also lifted their blockade of the United States.
Following the war, the New Englanders had a second debate and this time petitioned to be reincorporated into the British Empire. Now, however the person in charge was the Prince Regent (who would later become George IV in 1820) and not King George III and he agreed. After 39 years outside the British Empire (9 of which had been spent in war), New England had returned. By now, the New Englanders had lost their enthusiasm for republicanism following the second invasion by their former republican brothers in America.
**Note: at this point we can have the Commonwealth of New England become a British colony or the Commonwealth could be dissolved and the 5 New England states become 5 British colonies. From the text of the OP it doesn't strictly require a province of New England (although the OP title would require that). I think I'll do both....sort of...have New England annexed as a single colony and then upon Confederation have it split into 5 colonies just like how the province of Canada was split upon Confederation).**
In 1815 the Commonwealth of New England was annexed as the new British colony of New England (also called the province of New England).
Life from 1815-1867 continues as normal with the exception that New England is a British colony and the United States has a few more free states formed out of the northwest territory and upper louisiana purchase by the 1830s and 40s. Tensions rise in 1860s and Civil War breaks out. The Union crushes the south in 1866 - it doesn't start at exactly the same time and the the Union has a population of 19 million instead of the 22 million in OTL due to the absence of New England, but it still has more than the Confederacy which has 9 million people.
By the time of the Charlotte conference in 1864, New England had been back in the British empire for longer than it had been outside of it (49 years as opposed to 37 years of independent existence under the USA and then a republican New England).
During the war, there is a conference in Charlotte in 1864 about having a maritime union of Nova Scotia, New Brunswick, Prince Edward Island and Newfoundland (which is what had occurred in OTL). The provinces of New England and Canada (having faced American invasions in the War of 1812) have apprehension over the US in 1860s, especially as the Union military has vastly increased) ask to participate and eventually an agreement is hammered out.
Just for fun, we can have Newfoundland and Prince Edward Island agree to join the Confederation (they didn't in OTL and PEI joined later in 1873 after flirting with the idea of joining the USA and Newfoundland joined in 1949).
On another note, Prince Edward Island in 1770s had attempted to rename itself as "New Ireland" (from St. John's Island) but couldn't as only the Privy Council in Britain could officially rename colonies...If the Privy Council had decided to use the name New Ireland (if the name New Ireland had remained popular until the time PEI was finally renamed), then there would have been the region of New England and the colonies Nova Scotia, New Ireland and New Brunswick....maybe the whole area would have been called "New Britain"....but that's just an interesting side note.
So in 1867 the British North America Act is passed through the British Parliament providing for the Dominion of Canada which constituted the provinces of Ontario (I think that is the name the Privy Council would have still chosen), Quebec (both from the original colony called province of Canada), New Brunswick, Nova Scotia, Prince Edward Island, Newfoundland, and Maine, Massachussetts, Connecticut, Rhode Island, Vermont and New Hampshire (all formed from the original colony called the province of New England). The capital of Canada is still Ottawa (since that had been chosen as the capital of the province of Canada in 1857 as a compromise location between the English and French halves of the province of Canada and for the other reasons Ottawa was chosen (as is quoted from wikipedia below):
In fact, the Queen's advisers had her pick Ottawa for many important reasons: first, it was the only settlement of any significant size located right on the border of Canada East and Canada West (Quebec/Ontario border today), making it a compromise between the two colonies and their French and English populations; second, the War of 1812 had shown how vulnerable the major cities were to American attack, since they were all located very close to the border while Ottawa was (then) surrounded by a dense forest far from the border; third, the government owned a large parcel of land on a spectacular spot overlooking the Ottawa River. Ottawa's position in the back country made it more defensible, while still allowing easy transportation via the Ottawa River to Canada East, and the Rideau Canal to Canada West. Two other considerations were that Ottawa was at a point nearly exactly midway between Toronto and Quebec City (~500 km/310 mi) and that the small size of the town made it less likely that politically motivated mobs could go on a rampage and destroy government buildings, as had been the case in the previous Canadian capitals.
Note that Boston would have been seen as vulnerable (following the razing in 1792 and siege in 1812-1813) and would also have been susceptible to politically motivated mobs (Boston Tea Party that started the whole mess from the British perspective).
On a second note, following British tradition, New Hampshire is sometimes abbreviated as "New Hants."
In the Dominion of Canada the provinces are all represented according their population in the House of Representatives and in the Senate representation is equal but based on regions: So Ontario and Quebec have the same number of Senators as the Maritimes (Prince Edward Island, New Brunswick, Nova Scotia and Newfoundland) and Ontario, Quebec and the Maritimes all combined have the same number of Senators as New England (Maine, New Hampshire, Vermont, Massachussetts, Connecticut and Rhode Island). The population of Canada is about 7.1 million by 1870 with 12 provinces (by the way the population of Newfoundland was estimated at 130,000 in 1869 and this estimate was added to the 1871 Canada population and 1870 New England population I posted earlier).