I contacted Ron Canter, one of the three mappers of the Northern Forest Canoe Trail. Here is Ron’s response:
Fort Kent was chosen because the route first suggested for the trail didn’t go down the Allagash. It went east via Webster Brook, Grand Lake Matagamon, Beaver Brook, and the Aroostook, before turning north up the Little Machias to reach the Fish River and come down that to the St. Johns at Fort Kent, which was a major junction of ancient canoe routes.
The thought behind it was to not add to traffic on the Allagash, and to link to the Aroostook as well. When real work started on the trail, it was switched to the Allagash as a stopgap. It has worked so well, and with the Allagash no more crowded, that the Allagash quickly became the permanent route.
Madawaska might have worked as well as the terminus, but somehow it never occurred to us to consider it. A town like Fredericton, farther down the St. Johns, would have closed off some of the best options for extending the trail north or northeast into Canada in the future. A route up the Tobique and down the Nepisiguit through New Brunswick would be a particularly good fit for the NFCT.