Good question, Greg. "The Maritime Provinces" or just "The Maritimes" was a regional designation already before Newfoundland became part of Canada, with a well-established identity. Most Newfoundlanders felt when they joined Canada in 1949 that they did not join the region, and there are significant cultural differences. Canadians have now created the designation "Atlantic Canada" which includes both the Maritimes and Newfoundland.

It's sort of like asking why New York isn't part of New England. The reasons have to do with regional history and regional marketing rather than logic.