¿Por qué no puedo actualizar más de una columna al mismo tiempo usando la palabra clave With?

Esto parece funcionar (lo hizo con una consulta simple usando DUAL de todos modos):

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)
                                        );

En cuanto a por qué no funciona si la subconsulta comienza con "CON", solo puedo imaginar que se debe a que los diseñadores de Oracle SQL no habían previsto este uso.