How can I alter the primary key of an index-organized table?
An index-organized table (IOT) is just that; an index with no "real" table.  All data besides the primary key are just "tacked on" to the primary key, so for example if you have an IOT with 6 columns, 2 of which make up the primary key, behind the scenes you just have an index with 6 columns, of which the first 2 columns make it unique.

So, sorry, only way to fix it is to recreate the table; to improve the rebuild time temporarily disable logging.  You cannot use an append hint on inserts to an  IOT table to force a direct path insert: 

SQL&gt; CREATE TABLE books_new (
    title VARCHAR2(10),
    release_date DATE NOT NULL,
    CONSTRAINT pk_title PRIMARY KEY(title,release_date))
  ORGANIZATION INDEX NOLOGGING;

SQL&gt; INSERT INTO books_new 
     (SELECT title, '01-Jan-1980' FROM books);
SQL&gt; ALTER TABLE books_new LOGGING;
SQL&gt; ALTER TABLE books RENAME TO books_old;
SQL&gt; ALTER TABLE books_new RENAME TO books;