According to a U.S. Government Accountability Office (GAO) report to Congress the Defense Department awarded a contract for road construction in Afghanistan's Nuristan province back in 2004:
Table 1: USAID and Defense's Afghan Road Reconstruction Awards:
…
Year: 2004;
Project name–instrument used: CERP-funded road projects–Contracts;
Implementer: USACE or local contractors;
Project description: Provincial and rural roads, including Nangarej-
Mandol and Gulum Khan.Source: GAO analysis of USAID and Defense data.
(CERP is a Commander's Emergency Response Program under which a local U.S. commander spends money on urgent issues. USACE is the US Army Corps of Engineers.)
Still two years later, little seemed to have happened.
In 2006 a 'partnership agreement' was reached over the road project between Nangarej and Mandol. The army reported:
KABUL, Afghanistan – A partnership agreement was reached June 10 on the Nuristan Commander's Emergency Response Program's road projects at the district's headquarters here.
Attending the signing ceremony were Nuristan Governor Tamim Nuristani, Dr. Sayed Noorullah Jalili, chief executive of AMERIFA Construction Company and Col. Christopher J. Toomey, commander of the U. S. Army Corps of Engineers Afghanistan Engineer District/director of engineering for the Combined Forces Command – Afghanistan.
According to the partnership document, the three leaders agreed to "promote a climate of mutual respect, honest and open communication." The document also noted that the Coalition, contractor and government would be committed to proactive problem resolution in order to execute safe and timely construction in support of the infrastructure development of Nuristan on the Nangarej to Mandol and the Chapa Dara to Titan Dara CERP Road Projects.
Why did it take two years from a 'emergency fund' contract award to some actual agreement over building the road? We do not know. Maybe the the 'partnership document' was needed to clear away some stumbling blocks for the prospective road between Nangarej and Mandol.
According to FedSpending.org Amerifa, the Afghan company mentioned above, got contracts for road-building for $17 million in 2006 and $6.8 million in 2007. Wages there are $3-$5 per day, so that's a lot of dough. In November 2007, in an effort to "promote a climate of mutual respect, honest and open communication," the U.S. bombed a worker-camp of Amerifa in Nuristan. At least 14 were killed.
However, despite all these efforts the road-building that was awarded through an 'emergency response program' in 2004 is now back to its start.
A fresh solicitation for the Nangarej to Mandol road in Nuristan province was posted today on FedBizOpps.gov:
The U.S. Army corps of engineers, Afghanistan Engineer District intends to issue a Request fro Proposal (RFP) to award Firm Fixed Price contract to design and construct approximately 60 km of 6 m wide gravel road with 1.5 m gravel shoulder. The project is from Nangarej (70.33266E 35.05905N) to Mandal (70.101976E 35.165549N) in the Nuristan Province of Afghanistan.
Google Earth clip with those coordinates:

(the gray line is a province boarder, not the road)
So according to GAO a contract was awarded in 2004. In 2006 the road was not yet build but some agreement was found. Today the Army Corps of Engineer asks for a proposal on how to build the very same road (Mandal and Mandol are used interchangeably in various sources so it is very likely the same place).
With that speed of action the road will never be build.
That may well be because that road does not make any sense. Professor David Katz, an anthropologist who worked for the State Department and has been in Nuristan in a reconstruction project team, opines in a private lecture (video – start at 9:00min, helpful map (pdf)) that some of the plans for roads in Nuristan are crazy. These do not run along the natural river lines but try to connect independent areas (with quite different tribes and languages) over very rough mountains. Some of these roads are supposed to go over 15,000 feet high passes that are not accessible at all most of the year and there is "not a penny" to do maintenance on these roads once they are build.
Google Earth shows the coordinates given for Nangarej at 4,000 feet elevation, the coordinates for Mandal at some 10,000 feet. The distance as the crow flies is 25 kilometers. The recent solicitation is for 60 kilometers total road length. With that difference in elevation and the rough terrain, I find it unlikely that the project is doable as imagined.
Nuristanis will assess the speed of progress on such 'emergency' projects on their land. They will know that the crazy high-pass roads will immediately fall apart if they ever get build at all.
Why should they support the foreign people who are responsible for this? Indeed why should they tolerate their presence at all?