Al alterar el tipo de datos a varchar(4000) , haces que acepte NULLs .
Prueba esto:
ALTER TABLE [mytable] DROP CONSTRAINT PK_mytable_data;
ALTER TABLE [mytable] ALTER COLUMN data varchar(4000) NOT NULL;
ALTER TABLE [mytable] ADD CONSTRAINT PK_mytable_data PRIMARY KEY (fkid, data);
Tenga en cuenta que el tamaño del índice (que se crea implícitamente para PK ) está limitado a 900 los bytes y las inserciones de valores mayores fallarán.
