The project to build the undulating "Magic Carpet" roof - similar to that of Sir Norman's British Museum courtyard - had twice been approved by the city's National Capital Planning Commission.But it was rejected in a third vote after work had already started.
The commission ordered the Smithsonian Institution to redesign the project.
"We'll certainly go back [to the commission], hopefully in August or September," said Linda St Thomas of the Smithsonian.
She described the new work ''a modification'', but did not reveal how fundamental the changes might be. Some architectural experts suggested that they could be extensive.
The decision provoked fierce reactions from Sir Norman's supporters. Michael Beyard, of the Urban Land Institute, described the commission's ruling as "emblematic of the sorry state of architecture in the nation's capital".
While other cities were putting up exciting new buildings, Washington was "mired in a provincial and retrograde past", Mr Beyard said.
The Foster design envisions a glass canopy over the courtyard of the Old Patent Office. The 170-year-old building is used by the Smithsonian to house America's national portrait gallery and the American art museum, which were due to reopen next year after a six-year, £110 million refurbishment.
US watchdog halts Foster's glass roof
Heritage watchdogs have forced a halt to work on a £25 million glass canopy designed by Sir Norman Foster to link two of Washington's premier art galleries.