1881 Canadian census for St John NB both show Phelina and John as born in Ireland, not Scotland. 1901 census she’s a widow but again born in Ireland.
She married in Magheraculmoney parish church so was probably baptised there too. Their baptism records start in 1767. The records don’t appear to be on-line anywhere but there’s a copy in PRONI in Belfast. Personal visit required to view them.
The Armstrongs may well have Scottish origins given the surname, the location and religious denomination but their arrival from Scotland is likely to have been in the 1600s, when many “Border Reivers” as they were known were relocated to Ireland.