why are regional cruising altitudes higher than those of international much longer flights?
Flight altitudes have relatively little to do with whether a flight is regional or international per se. More important factors include the winds aloft and the individual aircraft capability.

In the case of the Winnipeg to Manchester flight, they were probably using the North Atlantic Track System (NATS). The winds aloft over the North Atlantic are generally out of the west. The routes of the tracks are arranged each day to take advantage of the those winds. The track system puts the eastbound aircraft on tracks and at altitudes that would maximize the tailwinds, and westbound aircraft on tracks and at altitudes that minimize the headwind.

Since the winds aloft in the northern hemisphere are more often than not westerly, the Winnipeg to Vancouver flight might well have been fighting a headwind, but the strongest winds aloft tend to occur in the mid 30s, which can mean that you can lessen the headwind by climbing higher.

Aircraft capability also plays a major role, and aircraft vary widely in what they can do altitude wise. For example, a 747-200 up against its max takeoff weight of 800,000+ lbs can initially climb to only about 31,000 feet (FL310), but towards the end of the flight can reach FL390 and above.