Karrie,
Regarding a possible Mi'kmaq connection, have you considered having an mtDNA test done? The mtDNA genome is passed down from mother to daughter, and if your haplogroup is European this would disprove all those rumors once and for all. Of course, a Native American haplogroup would not necessarily tell us which maternal ancestor was of Native American origin and you would need to do further research.
Regards,
Maurice