CREATE INDEX for long columns
Here is the information on the CREATE INDEX statement for DB2. You may also want to check these links on designing indexes and space requirements for indexes as they also deal with your question on what factors into index page space.

Based on the last link it would seem to me that the page size for the index would be your column lengths + the index overhead. This may take you beyond the page size for your table. (Maybe that is what is happening here.) You could also try to place your table in a bigger tablespace. It may place the index in a bigger page size as well.


  EDIT: I have tested this locally as well to see. Using Control Center
  I was able to get a more detailed picture of the error message. Per
  DB2: "Explanation: 
  
  The index could not be created or altered because the sum of the key
  column internal lengths would exceed the index key length limit. Also,
  an index cannot be created using a LONG VARCHAR, LONG VARGRAPHIC, or
  LOB column. If the index is defined on a typed table, there is
  additional index overhead that reduces the maximum length by 4 bytes.
  The index may be altered by an ALTER TABLE or ALTER NICKNAME statement
  that alters the data type of one or more columns.
  
  An index extension could not be created because the sum of the columns
  returned by the GENERATE KEY function would exceed the index key
  length limit.
  
  The index key length limit is based on the page size of the tablespace
  used by the index:

Max Key Length  Page size
--------------  ---------
1K              4K
2K              8K
4K              16K
8K              32K

  
  The statement cannot be processed. The specified index or index
  extension was not created or the table or nickname could not be
  altered.
  
  User response: 
  
  To modify the index definition or alter column, eliminate one or more
  key columns and reduce the key length to the permitted maximum. For an
  index extension definition, specify a different GENERATE KEY function,
  or redefine the function to reduce the length of the returned row."
  
  As mentioned in my comment below your key size would be at least 32 +
  (4000 * 2 (for UTF-16)) + 2 (for varchar length identifier) + index
  overhead, so you are already at 8034+ bytes. This means just over 7K.
  I'm guessing you are not defining a tablespace, so it will default to 
  USERSPACE1, which is an 8K tablespace), so you have a 2K max key length
  as shown by the table above, plus your error message). In order to make
  this key, you have to do one of two things
  
  
  Alter your table definition so it isn't so big (probably reduce your
  varchar size) so you can fit within a 1K max key definition. I'm
  guessing you don't want to do this so then you end doing the next one:
  Since your key space requires 8K key length, you need a 32K page size.
  You can leave the table in a default 4K tablespace, but the index MUST be in a 32K 
  tablespace. If you are using
  automatic storage you could easily create a tablespace with the
  following: 
  


create bufferpool BP32K immediate size 250 automatic pagesize 32K;
create large tablespace TS32K pagesize 32K managed by automatic
storage bufferpool BP32K; 
create table line (
  field_key   integer not null,
  value       varchar(4000),
  ... ) index in TS32K; 
create index key_value_idx on line (field_key, value);



  This will place the index in the 32K tablespace and you
  should be fine.