There are 8 tribal groups recognized in Virginia today:
Note that these reservations were made with the colony/state of Virginia. The Mattaponi and Pamunkey reservations were established by 1677 Treaty of Middle Plantation. These reservations were established before the start of the United States; there are no Federal treaties with Virginia's tribal groups (yet...). Fisheries management in the Pacific Northwest is dominated by legal disputes over treaty commitments made by the Federal government in the 1800's. However, there are no Native American treaties with the Federal government that affect harvest in the Chesapeake Bay region.
Virginia courts have ruled against a Mattaponi claim that the 1677 treaty should block consideration of a dam and reservoir proposed by Newport News on Cohoke Creek. The Attorney General of Virginia has declared that the state of Virginia owns the lands on which those Pamunkey and Mattoponi reservations are located. The tribes have exclusive use, but can not sell the land without state approval. The Attorney General also ruled that the King William County sheriff’s office "may exercise same law-enforcement authority on Pamunkey and Mattaponi Indian reservations as elsewhere in county — may serve legal process, arrest warrants, and subpoenas, and investigate misdemeanors and felonies."2
What happened to the 50,000 Native Americans in Virginia in 1607, including the 15,000 Algonquians living under Powhatan's control on the Coastal Plain? Many died from disease and direct conflicts with the English (mostly small-scale murder and skirmishes, but also open warfare in 1622 and 1644). Others migrated as individuals or family groups to the north, west, or south, away from the encroaching English. They joined the Iroquois, Shawnee, and Cherokee, losing their distinct identity as members in Virginia tribes.
Note that the map is different when you count population totals rather than population density:
The Bureau of Census has the challege of collecting population data by race and ethnicity. See the:
How will Native American populations change in the future? Here are the 2004 projections from the Bureau of Census report, Projected State Populations, by Sex, Race, and Hispanic Origin: 1995-2025
AMERICAN INDIAN, July 1, July 1, July 1, July 1, July 1, ESKIMO, ALEUT 1995 2000 2005 2015 2025 FEMALES Alabama............. 8 9 9 10 12 Alaska.............. 46 47 46 47 48 Arizona............. 125 135 143 157 171 Arkansas............ 7 8 8 9 10 California.......... 150 147 148 171 197 Colorado............ 18 20 23 27 31 Connecticut......... 4 4 4 5 6 Delaware............ 1 1 1 1 1 District of Columbia 1 0 0 0 0 Florida............. 22 25 29 35 42 Georgia............. 8 8 9 9 10 Hawaii.............. 3 3 3 4 4 Idaho............... 8 10 13 15 16 Illinois............ 12 13 14 17 20 Indiana............. 7 8 8 9 10 Iowa................ 4 4 6 7 7 Kansas.............. 11 14 15 16 18 Kentucky............ 3 3 3 4 4 Louisiana........... 10 10 10 11 13 Maine............... 3 3 3 3 4 Maryland............ 7 8 8 9 11 Massachusetts....... 7 7 7 8 10 Michigan............ 30 31 32 34 37 Minnesota........... 28 32 36 45 53 Mississippi......... 4 4 4 4 4 Missouri............ 11 12 13 15 16 Montana............. 27 31 34 40 47 Nebraska............ 7 8 9 11 13 Nevada.............. 13 16 16 16 17 New Hampshire....... 1 1 1 2 2 New Jersey.......... 10 10 12 13 15 New Mexico.......... 78 87 96 119 141 New York............ 36 38 40 45 49 North Carolina...... 45 48 50 53 56 North Dakota........ 14 16 19 24 30 Ohio................ 11 11 12 13 15 Oklahoma............ 136 144 151 170 187 Oregon.............. 22 26 28 32 37 Pennsylvania........ 8 9 11 12 13 Rhode Island........ 2 2 4 4 5 South Carolina...... 4 4 4 5 5 South Dakota........ 27 31 34 40 46 Tennessee........... 5 6 7 7 9 Texas............... 41 47 53 68 81 Utah................ 15 19 22 26 30 Vermont............. 1 1 1 1 1 Virginia............ 8 9 9 10 11 Washington.......... 50 54 58 68 77 West Virginia....... 1 1 1 1 1 Wisconsin........... 22 25 26 29 32 Wyoming............. 6 7 8 11 14 Projected State Populations, by Sex, Race, and Hispanic Origin: 1995-2025 (Numbers rounded to nearest thousand. Resident population. Series A projections. For more details, see PPL #47, "Population Projections for States, by Age, Sex, Race, and Hispanic Origin: 1995 to 2025.")
The concentration of Native Americans in the densely-populated regions of the state reflects the migration of non-Virginians into those fast-growing communities, rather than remnant populations that survived from colonial times.