You already have most of what I found, but I see a few breadcrumbs that may help your research.
He may have had a land grant in Sunbury County: https://archives.gnb.ca/Search/RS108/Details.aspx?culture=en-CA&Key=60941
I draw a blank on the 1851 Census, but I see a Grigoire and Margaret Tibodo in Shediac in 1861 Census with a son Samuel, who is close to the right age. : https://www.bac-lac.gc.ca/eng/census/1861/Pages/item.aspx?itemid=1329363
They all appear again in the 1871 Census except the parents are now listed as Grigoire and Marcelin, and the son is Anselm Tibodo born around 1845, which sounds like it might be right: https://www.bac-lac.gc.ca/eng/census/1871/Pages/item.aspx?itemid=709037
You may discover something more solid by researching his siblings listed in these two census files.
In secondary sources, I see some suggestions that Gregoire's wife was Marceline Theriault,
New Brunswick Genealogical Society provides many of the same sources for the Thibodeau family and the Theriault family
- Fidèle Thériault’s Les familles de Caraque
- Bona Arsenault’s Histoire et généalogie des Acadiens, V
- Thibodeau family history: Part 1, pages 34-36: Part 2, pages 12-13:
- Leo G. Cyr’s Madawaskan Heritage,
- Roger Paradis’ Papiers de/Papers of, Prudent L. Mercure, Histoire du Madawaska, Vol. III, Partie B, pgs 50-1.
Some of these require to you be in NB to review the document(s), but others may be available online.
Otherwise I might look for a way to get access to the Drouin or Tanguay records. They do a good job with the French Catholics of NB and Quebec, though both are behind a paywall, either directly or through Ancestry.com.