Questo sembra funzionare (lo ha fatto comunque con una semplice query 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)
);
Per quanto riguarda il motivo per cui non funziona se la sottoquery inizia con "CON", posso solo immaginare che sia perché i progettisti di Oracle SQL non avevano previsto questo utilizzo.