POD: 1619. The
Mangazeya trade route (aka the North-East Passage - modern
Northern Sea Route) doesn't get forbidden.
The Pomors thrive much more and much longer.
Russkoye Ustye (which appears to be founded pre-POD) is also a more significant town; so is
Anadyrsk (assuming it still exists).
Now, it being Pomors (i.e. sea-based) rather than Cossacks (mostly land-based), they probably won't have a problem with continuing on to Alyeska (which IOTL took another century). In fact, they might well occupy most of OTL Canadian Northwest Territories and a large bit of Nunavut (by land (river) as well as sea expansion - compare
Zashiversk for an OTL example: while it's mostly Pomors, the Cossacks aren't going to just disappear) by the 1660s... which is when the Hudson Bay Company comes in.
I would imagine that the Pomors and HBC could end up not meeting for several more years (the Pomors being more active in the north-western parts of Hudson's Bay and HBC in the south-eastern ones, that is, mostly James Bay); then they meet when the HBC guys arrive at the place that became
Port Nelson IOTL (which by then is a major Pomor village).
Here the hard part starts. The English would say that they were granted that land by the King. The Russians would say that they got there from the other side, and what does their King have to do with that faraway land. Then someone brings up the Navigation Acts... At the end, the Russians probably end up with the Nelson River basin (and everything to the North of it), while the British get to have their precious James Bay - remember that there haven't been much settlement yet in OTL Quebec (or Labrador), by either the British or the French (
this map shows the OTL situation in 1702; 1670s, I assume, would be even a little less).
At that point, I would imagine, some of the Russians find that one little loophole in the Rupert's Land definition... that is, that it doesn't include OTL Labrador, which is only a strait (the Hudson one) away from Russian lands at Baffin Island... and isn't really occupied by anyone else, at least in the northern part (honestly, looking at that 1702 map, in the southern part as well). In 1680 or so, the Russians take an opportunity to claim Labrador for themselves... by 1700, it's a full-fledged Russian colony.
Now, I assume Labrador counts as "a colony at least the size of OTL Vermont on the East Coast of North America"; as for the ASBs, I would be very interested if you manage to spot any

It's, of course, still a huge Russo-wank (more so if you realize that by then they actually own just about every part of OTL Canada but the actually populated areas, as well as most of Cascadia), but it would've taken something even more massive than
that to get Russia a colony on the East Coast in the usual way (as noted in this thread already).
I have no idea, though, how could they save that particular colony till 1800 (note, though, that nobody was really interested in Labrador historically, and 1700s is just the time for a
Great Northern Expedition analogue, so it isn't
too unlikely).