Dies scheint zu funktionieren (es hat sowieso mit einer einfachen Abfrage mit DUAL funktioniert):
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)
);
Warum es nicht funktioniert, wenn die Unterabfrage mit "WITH" beginnt, kann ich mir nur vorstellen, dass dies daran liegt, dass die Designer von Oracle SQL diese Verwendung nicht vorhergesehen haben.