Isso parece funcionar (de qualquer maneira, com uma consulta simples usando DUAL):
UPDATE Table_A SET (Col_One, Col_Two) = (select col_one, col_two from
(WITH OneValue AS (SELECT DISTINCT t.Col_One, T.Col_two
FROM Table_Two t, Table_A a
WHERE t.id = a.New_Id))
SELECT Col_One, Col_Two FROM OneValue)
);
Quanto ao motivo de não funcionar se a subconsulta começar com "WITH", só posso imaginar que seja porque os designers do Oracle SQL não previram esse uso.